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 ≤ n ≤ 2 ⋅ 10^5 , 1 ≤ l ≤ r ≤ 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.

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].
import java.util.Arrays;
import java.util.Scanner;

public class AyoubAndLostArray {
	static final int MOD=(int)1e9+7;
	static int n;
	static int mod0,mod1,mod2;
	public static void main(String[] args) {
		Scanner scan=new Scanner(System.in);
		n=scan.nextInt();
		int l=scan.nextInt(), r=scan.nextInt();
		dp=new long[n][3];
		for(long[] d:dp) Arrays.fill(d,-1);
		int total=r-l+1;
		mod0=total/3;
		mod1=total/3;
		mod2=total/3;
		if(total%3==1) {
			if(l%3==0) mod0++;
			if(l%3==1) mod1++;
			if(l%3==2) mod2++;
		}
		else if(total%3==2) {
			if(l%3==0) {
				mod0++;
				mod1++;
			}
			if(l%3==1) {
				mod1++;
				mod2++;
			}
			if(l%3==2) {
				mod2++;
				mod0++;
			}
		}
//		System.out.println(mod0+" "+mod1+" "+mod2);
		System.out.println(go(0,0));
	}
	static long[][] dp;
	public static long go(int at, int mod) {
		if(at==n) {
			if(mod!=0) return 0L;
			return 1L;
		}
		if(dp[at][mod]!=-1) return dp[at][mod];
		
		long res=0L;
		res=(res+(mod0*go(at+1,mod))%MOD)%MOD;
		res=(res+(mod1*go(at+1,(mod+1)%3))%MOD)%MOD;
		res=(res+(mod2*go(at+1,(mod+2)%3))%MOD)%MOD;
		
		return dp[at][mod]=res%MOD;
	}
}