C. Ayoub and Lost Array
combinatorics; dp; math
Ayoub had an array \(a\) of integers of size \(n\) and this array had two interesting properties: All the integers in the array were between \(l\) and \(r\) (inclusive). The sum of all the elements was divisible by \(3\). 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. 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\).
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.
Print the remainder when dividing by \(10^9 + 7\) the number of ways to restore the array.
In the first example, the possible arrays are : \([1,2], [2,1], [3, 3]\).In the second example, the only possible array is \([2, 2, 2]\).