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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

//import Number_theory.pair;

import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

//import graph_representation.edge;
public class hacker49 {
	public static int r1=0;
	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; 
        } 
    } 
//static 	ArrayList<Integer>[] f=new ArrayList[200001];
static 	int[] deg=new int[100001];
	static HashMap<Long,Integer> e=new HashMap<>();
	public static void main(String[] args) {
		OutputStream outputStream =System.out;
	    PrintWriter out =new PrintWriter(outputStream);
		FastReader s=new FastReader();
int n=s.nextInt();
long l=s.nextLong();
long r=s.nextLong();
long d1=r/3;
long d2=d1;
long d3=d1;
if(r%3==1) {
	d1++;
}else if(r%3==2) {
	d1++;
	d2++;
}
long d4=(l-1)/3;
long d5=d4;
long d6=d4;
if((l-1)%3==1) {
	d4++;
}else if((l-1)%3==2) {
	d4++;
	d5++;
}
long a=(d1-d4);
long b=(d2-d5);
long c=(d3-d6);
long[][] dp=new long[n+1][4];
dp[1][1]=a;
dp[1][2]=b;
dp[1][3]=c;
//System.out.println(a+" "+b+" "+c);
for(int i=2;i<=n;i++) {
dp[i][3]=(dp[i-1][3]*c)%mod;
dp[i][3]=(dp[i][3]+(dp[i-1][2]*a)%mod)%mod;
dp[i][3]=(dp[i][3]+(dp[i-1][1]*b)%mod)%mod;

dp[i][1]=((dp[i-1][3]*a)%mod +(dp[i-1][1]*c)%mod)%mod;
dp[i][1]=(dp[i][1]+(dp[i-1][2]*b)%mod)%mod;

dp[i][2]=((dp[i-1][3]*b)%mod +(dp[i-1][2]*c)%mod)%mod;
dp[i][2]=(dp[i][2]+(dp[i-1][1]*a)%mod)%mod;



}
//for(int i=1;i<=n;i++) {
//	for(int j=1;j<=3;j++) {
//	out.print(dp[i][j]+" ");
//	}
//	out.println();
//}
System.out.println(dp[n][3]);
out.close();

	}
	static long mod=1000000007;
	public static long GCD(long a,long b) {
		if(b==(long)0) {
			return a;
		}
		return GCD(b , a%b);
	}
	static long c=0;
	public static long res=1;
	public static void prime_factorization(long n) {
		for(long i=2;(long)(i*i)<=n;i++) {
			if(n%i==0) {
				long count=0;
				while(n%i==0) {
					count++;
					n/=i;
				}
//			prime_pairs.add(new pair(i,count));
//			res*=(count+1);
				c+=(count);
			}
		}
		if(n>1) {
//			prime_pairs.add(new pair(n,1));
//		res*=2;
			c+=(1);
		}
		
	}
	
		
	
}