題干：

Ayoub had an array?aa?of integers of size?nn?and this array had two interesting properties:

• All the integers in the array were between?ll?and?rr?(inclusive).
• The sum of all the elements was divisible by?33.

Unfortunately, Ayoub has lost his array, but he remembers the size of the array?nnand the numbers?ll?and?rr, 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+7109+7?(i.e. the remainder when dividing by?109+7109+7). In case there are no satisfying arrays (Ayoub has a wrong memory), print?00.

Input

The first and only line contains three integers?nn,?ll?and?rr?(1≤n≤2?105,1≤l≤r≤1091≤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+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][1,2],[2,1],[3,3].

In the second example, the only possible array is?[2,2,2][2,2,2].

解題報告：

? ?dp[i][j]表示選擇i個數可以組成模數為j的方案數。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e5 + 5; const ll mod = 1e9+7; int n,l,r; ll dp[MAX][3],num[3]; int main() {cin>>n>>l>>r;ll tmp = (r-l)/3;num[0] = r/3 - (l-1)/3;num[1] = (r+2)/3 - (l+1)/3;num[2] = (r+1)/3 - (l)/3;dp[0][0]=1;for(int i = 1; i<=n; i++) {for(int j = 0; j<3; j++) {for(int k = 0; k<3; k++) {dp[i][j] += dp[i-1][k]*num[(j+3-k)%3];}dp[i][j]%=mod;}} printf("%lld\n",dp[n][0]);return 0 ; }

也可以直接dp[1][0,1,2]都給初始化好。

總結

以上是生活随笔為你收集整理的【CodeForces - 1105C】Ayoub and Lost Array（线性计数dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。