CF1105C Ayoub and Lost Array

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