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.io.*;
import java.util.*;

public class A{

	static int n,cnt[];
	static int MOD=(int) (1e9+7);
	static int L,R;
	static void get() {
		
		for(int mod=0;mod<3;mod++) {
			cnt[mod]=get(R, mod)-get(L-1,mod);
		}
		
	}
	static int get(int r,int mod) {
		if(mod>r)
			return 0;
		return  (r-mod)/3+ (mod>0?1:0);
	}
	static int [][]memo;
	static int dp(int idx,int mod) {
		if(idx==n)
			return mod==0?1:0;
		if(memo[mod][idx]!=-1)
			return memo[mod][idx];
		long ans=0;
		for(int curr=0;curr<3;curr++)
		{
			int newMod=(mod+curr);
			if(newMod>=3)
				newMod-=3;
			ans=(ans+cnt[curr]*1l*dp(idx+1,newMod))%MOD;
			
		}
		return memo[mod][idx]=(int) ans;
	}
	public static void main(String[] args) throws IOException {
		Scanner sc=new Scanner();
		PrintWriter out=new PrintWriter(System.out);
		n=sc.nextInt();
		L=sc.nextInt();
		R=sc.nextInt();
		cnt=new int [3];
		memo=new int [3][n];
		for(int i=0;i<3;i++)
			Arrays.fill(memo[i], -1);
		get();
		out.println(dp(0, 0));
		out.close();

	}
	static class Scanner
	{
		BufferedReader br;
		StringTokenizer st;
		Scanner(){
			br=new BufferedReader(new InputStreamReader(System.in));
		}
		Scanner(String fileName) throws FileNotFoundException{
			br=new BufferedReader(new FileReader(fileName));
		}
		String next() throws IOException {
			while(st==null || !st.hasMoreTokens())
				st=new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		String nextLine() throws IOException {
			return br.readLine();
		}
		int nextInt() throws IOException{
			return Integer.parseInt(next());
		}
		long nextLong()  throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}
		double nextDouble() throws NumberFormatException, IOException {
			return Double.parseDouble(next());
		}
	}
}
