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 solution {
	
	static long mod  = ((long)(Math.pow(10, 9))) + 7;

    public static void main (String[] args) throws IOException{
    	FastReader f=new FastReader();

    	int n = f.nextInt();
    	int l = f.nextInt();
    	int r = f.nextInt();
    	
    	long[][] dp = new long[n+1][3];
    	
//    	for (int i=l;i<=r;i++) {
//    		dp[1][i%3] = dp[1][i%3]+1;
//    	}
//    	System.out.println(dp[1][0]+" "+dp[1][1]+" "+dp[1][2]+" ");
    	
    	int a0 =  (r+3)/3 - (l+2)/3;
    	int a1 = (r+2)/3 - (l+1)/3;
    	int a2 = (r-l+1) - a0 - a1;
    	
    	dp[1][0] = a0;
    	dp[1][1] = a1;
    	dp[1][2] = a2;
    	
    	
    	for (int i=2;i<=n;i++) {
    		for (int j=0;j<3;j++) {
    			dp[i][(0+j)%3] = (dp[i][(0+j)%3] + (a0*dp[i-1][j])%mod)%mod;
    			dp[i][(1+j)%3] = (dp[i][(1+j)%3] + (a1*dp[i-1][j])%mod)%mod;
    			dp[i][(2+j)%3] = (dp[i][(2+j)%3] + (a2*dp[i-1][j])%mod)%mod;
    		}
    	}
    	System.out.println(dp[n][0]%mod);
    }

    
    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; 
        } 
    } 
  
}

/*
 * 
 * 9 12 : 2 1 1
 * 9 13 : 2 2 1
 * 9 14 : 2 2 2
 * 
 * 8 12: 2 1 2
 * 7 12:   2
 * 
 * 8 13: 2 2 2
 * 
 * r ceil - l ceil
 * */
