332 · recovery array

Xiao Jiu has a long nnn Integer array , Every number in the array is in lll and rrr Between , And the sum of the array is 333 Integer multiple .
Please help Xiao Jiu calculate how many different possibilities there are in this array .
Output to 109+710^9+7109+7 modulus

The length of the array is nnn, Satisfy 1≤n≤1051 \le n \le 10^51≤n≤105.
Every element in the array satisfies ,l≤ai≤r,1≤l≤r≤109l \le a_i \le r, 1 \le l \le r \le 10^9l≤ai​≤r,1≤l≤r≤109.
In the example , Possible arrays are [1,2],[2,1],[3,3][1,2], [2, 1], [3, 3][1,2],[2,1],[3,3].

Examples

 Input ：
n = 2
l = 1
r = 3
 Output ：
3

//
// Important information ： Arrays and are 3 Multiple , Then we can find the remainder as 0,1,2 The combination number of
//
// hypothesis
//c0 The remainder is 0 The combination number of ,c1 The remainder is 1 The combination number of ,c2 The remainder is 2 The combination number of
//f0 representative l - r Remainder is 0 The number of ,f1 representative l - r Remainder is 1 The number of ,f2 representative l - r Remainder is 2 The number of
//
// The simple recursive method is ：
//1：dp[i][c0] = dp[i - 1][c0] * f0 + dp[i - 1][c2] * f1 + dp[i - 1][c1] * f2
//2: dp[i][c1] = dp[i - 1][c1] * f0 + dp[i - 1][c0] * f1 + dp[i - 1][c2] * f2
//3 : dp[i][c2] = dp[i - 1][c2] * f0 + dp[i - 1][c1] * f1 + dp[i - 1][c0] * f2
//
// Here's an optimization tip , Don't cycle l - r Every number of counts f0, f1, f2, That will time out , Now divide the quantity by 3 Just calculate the quantity , See the code for details.

int restoreArray(int n, int l, int r) {
    // write your code here.
    int mod = 1000000000 + 7;
    uint64_t f[3] = {0,0,0};
    int v = l;
    for (; v <= r && v % 3 != 1; v++)
    {
        f[v % 3]++;
    }
    int t = (r - v + 1) / 3;
    int e = (r - v + 1) % 3;
    f[0] += t;
    f[1] += t;
    f[2] += t;
    if (e >= 1) {
        f[1]++;
    }
    if (e > 1) {
        f[2]++;
    }
    uint64_t c[3] ;
    c[0] = f[0];
    c[1] = f[1];
    c[2] = f[2];
    uint64_t t0;
    uint64_t t1;
    uint64_t t2;
    for (int i = 1; i < n; i++)
    {
        t0 = c[0];
        t1 = c[1];
        t2 = c[2];
        c[0] = (f[0] * t0 + f[1] * t2 + f[2] * t1) % mod;
        c[1] = (f[0] * t1 + f[1] * t0 + f[2] * t2) % mod;
        c[2] = (f[0] * t2 + f[1] * t1 + f[2] * t0) % mod;
    }
    return (int)c[0];
}