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 nn and 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

Copy

2 1 3

Output

Copy

3

Input

Copy

3 2 2

Output

Copy

1

Input

Copy

9 9 99

Output

Copy

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

 

一道非常水的题，但是出了点状况，最后没完成。

令num[0/1/2]分别是[l,r]内对3取模为0/1/2的数的个数

设f(i,0/1/2):数组前i个元素和对3取模后为0/1/2的方案数。

f[i][0]=(f[i-1][0]*num[0]+f[i-1][1]*num[2]+f[i-1][2]*num[1])%mod
f[i][1]=(f[i-1][0]*num[1]+f[i-1][1]*num[0]+f[i-1][2]*num[2])%mod
f[i][2]=(f[i-1][0]*num[2]+f[i-1][1]*num[1]+f[i-1][2]*num[0])%mod

边界f[1][i]=num[i]

dp很水，但是那个统计模个数真的恶心，其实是自己没处理好，考虑l和r分别%3的值来分类的话，有3*3=9种情况，显然不能这样分类处理，那么稍微变一下不就行了吗。。

r-l<=3特殊处理，否则l加一点r减一点就很好处理了，见代码。

ab两道大水题做了好久，真是..一定要学会判断是水题还是什么题，别老往复杂想。

 

==================================后续：

那个预处理[l,r]有多少个数模3等于0/1/2的，转化为前r个数-前l个数。

num[0]=r/3-(l-1)/3    num[1]=(r+2)/3-(l+1)/3     num[2]=(r+1)/3-l/3

举几个例子就看出这样子是对的，而且很简单方便。

#include<bits/stdc++.h>
using namespace std;
#define mod (1000000007)

long long  n,l,r,f[200000+10][3];
long long num[3];

int main()
{
//	freopen("input.in","r",stdin);
	cin>>n>>l>>r;
	if(r-l>30)
	{
		while(l%3)
		{
			num[l%3]++;l++;
		}
		while(r%3)
		{
			num[r%3]++;r--;
		}
		num[0]+=(r-l)/3+1;
		num[1]+=(r-l)/3;
		num[2]+=(r-l)/3;
	}
	else for(int i=l;i<=r;i++)num[i%3]++;	
	 
	for(int i=0;i<3;i++)f[1][i]=num[i];
	for(int i=2;i<=n;i++)
	{
		f[i][0]=(f[i-1][0]*num[0]+f[i-1][1]*num[2]+f[i-1][2]*num[1])%mod;
		f[i][1]=(f[i-1][0]*num[1]+f[i-1][1]*num[0]+f[i-1][2]*num[2])%mod;
		f[i][2]=(f[i-1][0]*num[2]+f[i-1][1]*num[1]+f[i-1][2]*num[0])%mod;
	}
	//cout<<num[0]<<num[1]<<num[2];
	//cout<<num[0]<<num[1]<<num[2];
	cout<<f[n][0]<<endl;
	return 0;
}