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

public class Main {

    static FastReader in = new FastReader();
    static PrintWriter out = new PrintWriter(System.out);
    static long mod = (long)1e9+7;

    static void solve(){
        int n = in.nextInt(), l = in.nextInt(), r = in.nextInt();
        int x = 0,y = 0,z = 0,n1,n2;
        // // for 0
        // n1 = l%3==0?l:l+3-l%3;
        // n2 = r%3==0?r:r-r%3;
        n1 = l; n2 = r;
        if(n1%3==1)n1 = l+2;
        else if(n1%3==2)n1 = l+1;
        if(n2%3==1)n2 = r-1;
    	else if(n2%3==2)n2 = r-2;

        if(n1<=r && n2>=l){
        	x = (n2-n1)/3+1;
        }
        //for 1

         // out.println(n1+" "+n2);

        // n1 = l%3==1?l:l+l%3+1;
        // n2 = r%3==0?r-2:r-(r%3-1);
        n1 = l;
        n2 = r;
        if(n1%3==0)n1 = l+1;
        else if(n1%3==2)n1 = l+2;
        if(n2%3==0)n2 = r-2;
        else if(n2%3==2)n2 = r-1;
        if(n1<=r && n2>=l){
        	y = (n2-n1)/3+1;
        }
         // out.println(n1+" "+n2);

        //for 2
        n1 = l%3==2?l:l+2-l%3;
        n2 = r;
        if(r%3==0)n2 = r-1;
        else if(r%3==1) n2 = r-2;
        if(n1<=r && n2>=l){
        	z = (n2-n1)/3+1;
        }
      
        long[][] dp = new long[n+1][3];
        dp[1][0] = x;
        dp[1][1] = y;
        dp[1][2] = z;
        for(int i=2;i<=n;i++){
        	 dp[i][0] = (dp[i-1][0]*x+dp[i-1][1]*z+dp[i-1][2]*y)%mod;
        	 dp[i][1] = (dp[i-1][0]*y+dp[i-1][1]*x+dp[i-1][2]*z)%mod;
        	 dp[i][2] = (dp[i-1][0]*z+dp[i-1][1]*y+dp[i-1][2]*x)%mod;
        	
        }
        out.println(dp[n][0]);
    }


    public static void main(String[] args) {
        solve();
        out.flush();
        out.close();
    }

    static class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next(){
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        String nextLine(){
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                e.printStackTrace();
            }  
            return str;
        }
        int nextInt(){return Integer.parseInt(in.next());}
        long nextLong(){return Long.parseLong(in.next());}
        double nextDouble(){return Double.parseDouble(in.next());}
    }
    static class pair{
        int f,s;
        public pair(int f,int s){
            this.f = f;
            this.s = s;
        }
    }
}
