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.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

public class q5 {
	 
	 
	  
	  
	
	
	 
	
	 
	 
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		
		Reader.init(System.in);
		StringBuffer output=new StringBuffer("");
		PrintWriter out=new PrintWriter(System.out);
		int n=Reader.nextInt();
		int l=Reader.nextInt();
		int r=Reader.nextInt();
		if(l==r) {
			if(n%3==0) {
				output.append(1);
			}
			else {
				output.append(0);
			}
		}
		else {
			int numavailable=r-l+1;
			long mod=1000000007;
			long[][] dp=new long[n][3];
			long one=0,two=0,three=0;
			if(l%3==0) {
				three=dp[0][0]=(long)Math.ceil((double)numavailable/3);
				one=dp[0][1]=(long)Math.ceil(((double)numavailable-1)/3);
				two=dp[0][2]=(long) Math.ceil((double)(numavailable-2)/3);
			}
			else if(l%3==1) {
				one=dp[0][1]=(long)Math.ceil((double)numavailable/3);
				two=dp[0][2]=(long)Math.ceil(((double)numavailable-1)/3);
				three=dp[0][0]=(long) Math.ceil((double)(numavailable-2)/3);
			}
			else {
				two=dp[0][2]=(long)Math.ceil((double)numavailable/3);
				three=dp[0][0]=(long)Math.ceil(((double)numavailable-1)/3);
				one=dp[0][1]=(long) Math.ceil((double)(numavailable-2)/3);
			}
			for(int i=1;i<n;i++) {
				dp[i][0]=(dp[i-1][0]*three)%mod+ (dp[i-1][1]*two)%mod+(dp[i-1][2]*one)%mod;
				dp[i][0]%=mod;
				dp[i][1]=(dp[i-1][1]*three)%mod+(dp[i-1][0]*one)%mod+(dp[i-1][2]*two)%mod;
				dp[i][1]%=mod;
				dp[i][2]=(dp[i-1][2]*three)%mod+(dp[i-1][1]*one)%mod+(dp[i-1][0]*two)%mod;
			
			}
			output.append(dp[n-1][0]);
		}
		out.write(output.toString());
		out.flush();
	}
}

 


 
 class Reader {
	    static BufferedReader reader;
	    static StringTokenizer tokenizer;
	 
	    /** call this method to initialize reader for InputStream */
	    static void init(InputStream input) {
	        reader = new BufferedReader(
	                     new InputStreamReader(input) );
	        tokenizer = new StringTokenizer("");
	    }
	 
	    /** get next word */
	    static String nextLine() throws IOException{
	    	return reader.readLine();
	    }
	    static String next() throws IOException {
	        while ( ! tokenizer.hasMoreTokens() ) {
	            //TODO add check for eof if necessary
	            tokenizer = new StringTokenizer(
	                   reader.readLine() );
	        }
	        return tokenizer.nextToken();
	    }
	    
	    static int nextInt() throws IOException {
	        return Integer.parseInt( next() );
	    }
	    static long nextLong() throws IOException {
	        return Long.parseLong( next() );
	    }
	    static double nextDouble() throws IOException {
	        return Double.parseDouble( next() );
	    }
	}
