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 Solution
{
    static class Reader {
		BufferedReader br;
		StringTokenizer st;
 
		public Reader() {
			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;
		}
 
	}
    static class Ele implements Comparable<Ele> 
    {  
        public int x,y,z;  
        Ele(long x1,long y1,long z1) 
        {  
            x=(int)x1;y=(int)y1;z=(int)z1;
        }  
        public int compareTo(Ele ob) {  
        if(ob.x!=x)return x-ob.x;
        return this.y-ob.y;  
        }   
        public String toString()
        {
        	return "["+x+","+y+","+z+"]";
        }
    }
    static class MyMath
    {
    	int mod=(int)1e9+7;
    	long binExp(long a,long b)
    	{
    		a=a%mod;
    		long r=1;
    		while (b>0)
    		{
    			if ((b&1)>0)
    				r=(r*a)%mod;
    			a=a*a%mod;
    			b>>=1;
    		}
    		return r;
    	}
    	boolean[] seive(int n)
    	{
    		boolean p[]=new boolean[n+1];
    		p[0]=true;p[1]=true;
    		for (int i=2;i*i<=n;i++)
    		{
    			if (!p[i])
    			{
    				for (int j=2*i;j<=n;j+=i)p[j]=true;
    			}
    		}
    		return p;
    	}
	    long gcd(long max,long min)
	    {
	        long a;
	        while (max%min!=0)
	        {
	            a=max%min;
	            max=min;min=a;
	        }
	        return min;
	    }

	}
    int dp[][];

	public static void main(String[] args) throws IOException 
	{
		Reader sc=new Reader();Solution G=new Solution();MyMath mm=new MyMath();
		PrintWriter o = new PrintWriter(System.out);
		int t=1;//t=sc.nextInt();
		int x,x0,x1,x2;int y,y0,y1,y2;int s,s0,s1,s2;
		int n,m;int a[],b[],in[],in1[];
		long k,l;boolean v[],b1,b2;String ss;char c1[];
		//long l;long a[]; 
		ArrayList<ArrayList<Integer>> ll=new ArrayList<>();
		ArrayList<Integer> a1=new ArrayList<>();
		ArrayList<Integer> a2=new ArrayList<>();
		ArrayList<Integer> a3=new ArrayList<>();
		ArrayDeque<Integer> dq=new ArrayDeque<>();
		TreeSet<Integer> h0=new TreeSet<>();
		TreeSet<Integer> h1=new TreeSet<>();
		HashMap<Integer,Integer> h=new HashMap<>();
		try{
		while (t-->0)
		{
		    n=sc.nextInt();x0=sc.nextInt();x1=sc.nextInt();k=0;l=0;y=(x1-x0)/3;
		    y0=(x1-x0)/3;y1=(x1-x0)/3;y2=(x1-x0)/3;int mod=(int)1e9+7;
		    for (int  i=x0+y*3;i<=x1;i++)
		    {
		        if (i%3==0)y0++;if (i%3==1)y1++;if (i%3==2)y2++;
		        
		    }
		    long dp[][]=new long[n+1][3];
		    dp[0][0]=1;
		    a=new int[3];
		    a[0]=y0;a[1]=y1;a[2]=y2;
		    for (int i=1;i<=n;i++)
		    {
		        for (int j=0;j<3;j++)
		        {
		            for (int kk=0;kk<3;kk++)
		            {
		                dp[i][(j+kk)%3]=(dp[i][(j+kk)%3]+dp[i-1][j]*a[kk])%mod;
		                
		            }
		        }
		        //Ele ob=new Ele(dp[i][0],dp[i][1],dp[i][2]);
		        //o.println(ob);
		    }
		    o.println(dp[n][0]);
		    //o.println();
		    //o.println(h);
		    //o.println(x2);
		    //o.println();
		    h0.clear();ll.clear();a1.clear();a2.clear();h1.clear();h.clear();
		}
		}
		catch (Throwable e)
		{
		    e.printStackTrace();
		}
		//o.println("HI");
		
        o.flush();
        o.close();
	}
} 