codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1105C.md (1371B)


      1 Source: https://codeforces.com/problemset/problem/1105/C
      2 
      3 C. Ayoub and Lost Array
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Ayoub had an array $a$ of integers of size $n$ and this array had two interesting properties:
     22 
     23 * All the integers in the array were between $l$ and $r$ (inclusive).
     24 * The sum of all the elements was divisible by $3$.
     25 
     26 Unfortunately, Ayoub has lost his array, but he remembers the size of the array $n$ and the numbers $l$ and $r$, so he asked you to find the number of ways to restore the array.
     27 
     28 Since the answer could be very large, print it modulo $10^9 + 7$ (i.e. the remainder when dividing by $10^9 + 7$). In case there are no satisfying arrays (Ayoub has a wrong memory), print $0$.
     29 
     30 Input
     31 
     32 The first and only line contains three integers $n$, $l$ and $r$ ($1 \le n \le 2 \cdot 10^5 , 1 \le l \le r \le 10^9$) — the size of the lost array and the range of numbers in the array.
     33 
     34 Output
     35 
     36 Print the remainder when dividing by $10^9 + 7$ the number of ways to restore the array.
     37 
     38 Examples
     39 
     40 Input
     41 
     42 ```
     43 2 1 3
     44 ```
     45 
     46 Output
     47 
     48 ```
     49 3
     50 ```
     51 
     52 Input
     53 
     54 ```
     55 3 2 2
     56 ```
     57 
     58 Output
     59 
     60 ```
     61 1
     62 ```
     63 
     64 Input
     65 
     66 ```
     67 9 9 99
     68 ```
     69 
     70 Output
     71 
     72 ```
     73 711426616
     74 ```
     75 
     76 Note
     77 
     78 In the first example, the possible arrays are : $[1,2], [2,1], [3, 3]$.
     79 
     80 In the second example, the only possible array is $[2, 2, 2]$.