Preparing NOJ # Ayoub and Lost Array

1000ms 262144K

## Description:

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

## Input:

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.

## Output:

Print the remainder when dividing by $10^9 + 7$ the number of ways to restore the array.

## Sample Input:

 2 1 3

## Sample Output:

 3

## Sample Input:

 3 2 2

## Sample Output:

 1

## Sample Input:

 9 9 99

## Sample Output:

 711426616

## Note:

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

Info Provider CodeForces

Code CF1105C

Tags

combinatoricsdpmath

Submitted 94

Passed 35

AC Rate 37.23%

Date 03/04/2019 16:49:38

Related

Nothing Yet