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 Code534C {
	
	public static Vector<Long> f(int n, long mat[][])
	{
		if(n==0)
		{
			Vector<Long> vs= new Vector<Long>() ;
			vs.add((long)1) ;vs.add((long) 0) ;vs.add((long) 0) ;
			return vs ;
		}
		if(n==1)
		{
			Vector<Long> vs= new Vector<Long>() ;
			vs.add(mat[0][0]) ;vs.add(mat[0][1]) ;vs.add(mat[0][2]) ;
			return vs ;
		}
		else
		{
			Vector<Long> v= (f(n-1,mat)) ;
			for(int i=0 ; i<3 ;i++)
				v.set(i,v.elementAt(i)%(1000000007)) ;
			Vector<Long> ve = new Vector<Long>() ;
			long h0=0 ;
			for(int i=0 ; i<3 ;i++)
				h0+=((v.elementAt(i)*mat[i][0])%(1000000007)) ;
			h0=h0%(1000000007) ;
			long h1=0 ;
			for(int i=0 ; i<3 ;i++)
				h1+=((v.elementAt(i)*mat[i][1])%(1000000007)) ;
			h1=h1%(1000000007) ;
			long h2=0 ;
			for(int i=0 ; i<3 ;i++)
				h2+=((v.elementAt(i)*mat[i][2])%(1000000007)) ;
			h2=h2%(1000000007) ;
			ve.add(h0) ;ve.add(h1) ;ve.add(h2) ;
			return ve ;
			
		}
	}

	public static void main(String[] args) throws IOException 
	{
		BufferedReader jk = new BufferedReader(new InputStreamReader(System.in)) ;
		StringTokenizer ana = new StringTokenizer(jk.readLine()) ;
		int n = Integer.parseInt(ana.nextToken()) ;
		long l = Long.parseLong(ana.nextToken()) ;
		long r = Long.parseLong(ana.nextToken()) ;
		long mat[][] = new long[3][3] ;
		long dif = r-l+1 ;
		long h = dif/3 ;
		
		long te = dif%3 ;
		if(te==0)
		{
			for(int i=0 ; i<3 ;i++)
			{
				for(int j=0 ; j<3 ;j++)
				{
					mat[i][j]=h ;
				}
			}
		}
		else if(te==1)
		{
		    int re = (int) (l%3) ;	
		    re=(2*re)%3 ;
			for(int i=0 ; i<3 ;i++)
			{
				for(int j=0 ; j<3 ;j++)
				{
					 mat[i][j]=h ;
				}
			}
			for(int i=0 ; i<3 ;i++)
			{
				mat[i][(re+i)%3]++ ;
			}
		}
		else
		{
			int re = (int) (l%3) ;	
		    re=(re+2)%3 ;
		    re=(2*re)%3 ;
			for(int i=0 ; i<3 ;i++)
			{
				for(int j=0 ; j<3 ;j++)
				{
					 mat[i][j]=h+1 ;
				}
			}
			for(int i=0 ; i<3 ;i++)
			{
				if(mat[i][(re+i)%3]>0) mat[i][(re+i)%3]-- ;
			}
		}
		
		Vector<Long> v = f(n-1,mat) ;
 		long resu =0 ; 
 		long l0=mat[0][0] ; long l1=mat[0][2] ;long l2=mat[0][1] ;
 		
 		resu+=((v.elementAt(0)*l0)%(1000000007)) ;
 		resu+=((v.elementAt(1)*l1)%(1000000007)) ;
 		resu+=((v.elementAt(2)*l2)%(1000000007)) ;
 		System.out.println(resu%(1000000007));

	}

}
