Codeforces 1105C： Ayoub and Lost Array（递推）

time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

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 109+710^9+7109+7 (i.e. the remainder when dividing by 109+710^9+7109+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≤n≤2⋅105,1≤l≤r≤109)(1≤n≤2⋅10^5,1≤l≤r≤10^9)(1≤n≤2⋅105,1≤l≤r≤109) — the size of the lost array and the range of numbers in the array.

Output

Print the remainder when dividing by 109+710^9+7109+7 the number of ways to restore the array.

Examples

input
2 1 3
output
3
input
3 2 2
output
1
input
9 9 99
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]$.

题意

给出三个整数$n,l,r$，要求在$[l,r]$之间的数组成的长度为$n$的序列的和能够整除$3$

AC代码

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <limits.h>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <set>
#include <string>
#include <time.h>
#define ll long long
#define ull unsigned long long
#define ms(a,b) memset(a,b,sizeof(a))
#define pi acos(-1.0)
#define INF 0x7f7f7f7f
#define lson o<<1
#define rson o<<1|1
#define bug cout<<"-------------"<<endl
#define debug(...) cerr<<"["<<#__VA_ARGS__":"<<(__VA_ARGS__)<<"]"<<"n"
const double E=exp(1);
const int maxn=1e6+10;
const int mod=1e9+7;
using namespace std;
ll dp[3][maxn];
int n, l, r, t ;
int main(int argc, char const *argv[])
{
ios::sync_with_stdio(false);
cin>>n>>l>>r;
int num0,num1,num2;//余数为i的个数
num0=r/3-(l-1)/3;
num1=r/3+(r%3>=2)-(l-1)/3-((l-1)%3>=2);
num2=r-l+1-num0-num1;
dp[0][1]=num0;
dp[1][1]=num1;
dp[2][1]=num2;
for(int i=2;i<=n;i++)
{
dp[0][i]=((dp[0][i-1]%mod*(num0%mod))%mod+(dp[1][i-1]%mod*num2%mod)%mod+(dp[2][i-1]%mod*num1%mod)%mod)%mod;
dp[1][i]=((dp[0][i-1]%mod*(num1%mod))%mod+(dp[1][i-1]%mod*num0%mod)%mod+(dp[2][i-1]%mod*num2%mod)%mod)%mod;
dp[2][i]=((dp[0][i-1]%mod*(num2%mod))%mod+(dp[1][i-1]%mod*num1%mod)%mod+(dp[2][i-1]%mod*num0%mod)%mod)%mod;
}
cout<<dp[0][n]%mod<<endl;
return 0;
}