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]$.