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 Main {
    static BufferedReader br;
     static long mod = 1000000000 +7;
    public static void main(String[] args) throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));
          int tc = 1;
        //tc= cinI();
      while(tc-->0){
          
       
              String[] arr =cinA();
              int n = getI(arr[0]);
              int  l = getI(arr[1]);
              int r =  getI(arr[2]);
              if(l!=r){
             // int z  = (r/3) - ((l-1)/3);
            //  int o = (r-l+1-z)/2;
           //   System.out.println(z+ " "+o);
              
              long[][] dp  = new long[n][3];
              long[] di = new long[4];
               di[3]=r/3-(l-1)/3;
               di[2]=(r+2)/3-(l-1+2)/3;
               di[1]=(r+1)/3-(l-1+1)/3;
               //System.out.println(di[3]+" "+di[1]+" "+di[2]+" ");
              dp[0][0]=di[3];
              dp[0][1]=di[1];
              dp[0][2]=di[2];
              
              for(int j=1;j<n;j++){
                  long x = dp[j-1][0]%mod;
                  long y = dp[j-1][1]%mod;
                  long p =dp[j-1][2]%mod;
                  dp[j][0]=(((x*di[3])%mod)+((y*di[2])%mod)+((p*di[1])%mod))%mod;
                  dp[j][1]=(((x*di[1])%mod)+((y*di[3])%mod)+((p*di[2])%mod))%mod;
                  dp[j][2]=(((x*di[2])%mod)+((p*di[3])%mod)+(y*di[1]))%mod;
              }
              System.out.println(dp[n-1][0]);
              }
              else{
                  int x  =l%3;
                  if(x==0){
                      System.out.println(1);
                      
                      System.exit(0);
                  }
                  if((x*n)%3==0){
                       System.out.println(1);
                      
                      System.exit(0);
                  }
                  System.out.println(0);
              }
                   
                       
                       
                   }
               }
            //   for(int j=0;j<n;j++){
            //       for(int k=0;k<m;k++){
            //           System.out.print(dp[j][k]+" ");
            //       }
            //       System.out.println(" ");
            //   }
             
               
      
    
         
    
    public static int binary(long val,long[] arr){
    //    System.out.println("value "+ val);
        int i=0;
        int mid= 0;
        int e = arr.length;
        while(i<=e){
        //    System.out.println(i+ " "+e);
            
            mid = (i+e)/2;
            
            if(arr[mid]==val){
                
                return mid;
            }
            if(arr[mid]>val){
                
                e=mid-1;
                continue;
            }
            i=mid+1;
            
        }
       // System.out.println(mid);
        return mid;
    }
    

  
    
    public static void arrinit(String[] a,long[] b)throws Exception{
        for(int i=0;i<a.length;i++){
            b[i]=Long.parseLong(a[i]);
        }
    }
    public static void arrinit(String[] a,int[] b)throws Exception{
        for(int i=0;i<a.length;i++){
            b[i]=Integer.parseInt(a[i]);
        }
    }


    static double findRoots(int a, int b, int c) {
        // If a is 0, then equation is not
        //quadratic, but linear


        int d = b * b - 4 * a * c;
        double sqrt_val = Math.sqrt(Math.abs(d));


        // System.out.println("Roots are real and different \n");

        return Math.max((double) (-b + sqrt_val) / (2 * a),
                (double) (-b - sqrt_val) / (2 * a));


    }

    public static String cin() throws Exception {
        return br.readLine();
    }

    public static String[] cinA() throws Exception {
        return br.readLine().split(" ");
    }
  public static String[] cinA(int x) throws Exception{
      return br.readLine().split("");
  }

    public static String ToString(Long x) {
        return Long.toBinaryString(x);
    }

    public static void cout(String s) {
        System.out.println(s);
    }

    public static Integer cinI() throws Exception {
        return Integer.parseInt(br.readLine());
    }

    public static int getI(String s) throws Exception {
        return Integer.parseInt(s);
    }

    public static long getL(String s) throws Exception {
        return Long.parseLong(s);
    }

    public static int max(int a, int b) {
        return Math.max(a, b);
    }

    public static void coutI(int x) {
        System.out.println(String.valueOf(x));
    }

    public static void coutI(long x) {
        System.out.println(String.valueOf(x));
    }

    public static Long cinL() throws Exception {
        return Long.parseLong(br.readLine());
    }

    public static void arrInit(String[] arr, int[] arr1) throws Exception {
        for (int i = 0; i < arr.length; i++) {
            arr1[i] = getI(arr[i]);
        }

    }
}

class range {
    int l;
    int r;
    int diff;

    public range(int l, int r, int diff) {
        this.l = l;
        this.r = r;
        this.diff = diff;
    }
}

class sortRange implements Comparator<range> {


    @Override
    public int compare(range range, range t1) {
        if (range.diff != t1.diff)
            return t1.diff - range.diff;
        return range.l - t1.l;
    }
}