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 FastReader sc=null;
	static long mod=(long)1e9 + 7;
	
	public static void main(String[] args) {
		sc=new FastReader();
		int n=sc.nextInt(),l=sc.nextInt(),r=sc.nextInt();
		long dp[][]=new long[n][3];
		//dp[i][j] -> no such that sum until i has remainder of j
		int counts[]=new int[3];
		int all=(r-l+1);
		Arrays.fill(counts, all/3);
		int m=all%3;
		if(m==1)counts[l%3]++;
		if(m==2) {
			counts[l%3]++;
			counts[(l+1)%3]++;
		}
		for(int i=0;i<3;i++)dp[0][i]=counts[i];
		//print(counts);
		//dp[i][j] -> dp[i-1][j]*counts(0)+ dp[i-1][(j+1)%3]*counts[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][(j-k+3)%3]*counts[k];
				}
				dp[i][j]=dp[i][j]%mod;
			}
		}
		long ans=0;
		ans=(dp[n-1][0])%mod;
		System.out.println(ans);
		
			
			
		
		
		
		
	}
	static long mul(long a ,long b) {
		return (a*(b%mod)+mod)%mod;
	}
	
	//Binary Exponentiation
	static long exp(long base,long e) {
		if(e==0) return 1;
		long half=exp(base,e/2);
		if(e%2==0)return mul(half,half);
		return mul(half,mul(half,base));
	}
	
	//Mod Inverse
	static long modInv(long a) {
		return exp(a,mod-2);
	}
	
	
	
	
	
	
	
 
	
	static int[] reverse(int a[]) {
		ArrayList<Integer> al=new ArrayList<>();
		for(int i:a)al.add(i);
		Collections.sort(al,Collections.reverseOrder());
		for(int i=0;i<a.length;i++)a[i]=al.get(i);
		return a;
	}
	static int gcd(int a,int b) {
		if(b==0)return a;
		else return gcd(b,a%b);
	}
	static int[] ruffleSort(int a[]) {
		ArrayList<Integer> al=new ArrayList<>();
		for(int i:a)al.add(i);
		Collections.sort(al);
		for(int i=0;i<a.length;i++)a[i]=al.get(i);
		return a;
	}
	
	
	
	static void print(int a[]) {
		for(int e:a) {
			System.out.print(e+" ");
		}
		System.out.println();
	}
	static void print(long a[]) {
		for(long e:a) {
			System.out.print(e+" ");
		}
		System.out.println();
	}
	
	
	static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
        int[] readArray(int n) {
    		int a[]=new int [n];
    		for(int i=0;i<n;i++) {
    			a[i]=sc.nextInt();
    		}
    		return a;
    	}
    } 
}
