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.IOException;
import java.io.InputStream;
import java.util.*;
public class sol {
    static long mod = (long)Math.pow(10,9)+7;
    static long p=998244353;
    static StringBuilder sb = new StringBuilder();
    static ArrayList<Integer> adj[];
    static boolean vis[];
    static long a[];
    public static void main(String args[])throws Exception {
        FastReader in = new FastReader(System.in); 
        int t=1,i,j;
        start:while(t-->0) { 
            int n=in.nextInt(),l=in.nextInt(),r=in.nextInt();
            a = new long[3];
            int max=r-l+1;
            int x=max/3;
            for(i=0;i<3;i++)
                a[i]=x;
            if(max%3==1)
                a[l%3]++;
            else if(max%3==2) {
                a[l%3]++;
                a[(l+1)%3]++;
            }
            //System.out.println(a[0]+" "+a[1]+" "+a[2]);
            long dp[][]=new long[n][3];
            for(i=0;i<3;i++)
                dp[0][i]=a[i];
            for(i=1;i<n;i++) {
                dp[i][0]=((dp[i-1][0]*a[0])%mod + (dp[i-1][1]*a[2])%mod + (dp[i-1][2]*a[1])%mod) %mod;
                dp[i][1]=((dp[i-1][0]*a[1])%mod + (dp[i-1][1]*a[0])%mod + (dp[i-1][2]*a[2])%mod) %mod;
                dp[i][2]=((dp[i-1][0]*a[2])%mod + (dp[i-1][1]*a[1])%mod + (dp[i-1][2]*a[0])%mod) %mod; 
            }
            System.out.println(dp[n-1][0]%mod);
        }
        //System.out.print(sb);
    }
    static long power(long a, long b) {
        if(b == 0)
            return 1L;
        long val = power(a, b / 2);
        if(b % 2 == 0)
            return val * val % mod;
        else 
            return val * val % mod * a % mod;
    }
    static void merge(int arr[], int l, int m, int r) {
        int n1 = m - l + 1; 
        int n2 = r - m; 
        int L[] = new int [n1]; 
        int R[] = new int [n2]; 
        for (int i=0; i<n1; ++i) 
            L[i] = arr[l + i]; 
        for (int j=0; j<n2; ++j) 
            R[j] = arr[m + 1+ j]; 
        int i = 0, j = 0; 
        int k = l; 
        while (i < n1 && j < n2) { 
            if (L[i] <= R[j]) { 
                arr[k] = L[i]; 
                i++; 
            } 
            else { 
                arr[k] = R[j]; 
                j++; 
            } 
            k++; 
        } 
        while (i < n1) { 
            arr[k] = L[i]; 
            i++; 
            k++; 
        } 
        while (j < n2) { 
            arr[k] = R[j]; 
            j++; 
            k++; 
        } 
    }  
    static void sort(int arr[], int l, int r) { 
        if (l < r) {
            int m = (l+r)/2; 
            sort(arr, l, m); 
            sort(arr , m+1, r); 
            merge(arr, l, m, r); 
        } 
    } 
    static int gcd(int a, int b) { 
        if (b == 0) 
            return a; 
        return gcd(b, a % b);  
    }
    static class Pair { 
        int a; 
        int b;  
        Pair(int x, int y) { 
            a = x; 
            b = y; 
        } 
    }
}
class FastReader {
    byte[] buf = new byte[2048];
    int index, total;
    InputStream in;
    FastReader(InputStream is) {
        in = is;
    }
    int scan() throws IOException {
        if (index >= total) {
            index = 0;
            total = in.read(buf);
            if (total <= 0) {
                return -1;
            }
        }
        return buf[index++];
    }
    String next() throws IOException {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        StringBuilder sb = new StringBuilder();
        for (; c > 32; c = scan()) {
            sb.append((char) c);
        }
        return sb.toString();
    }
    String nextLine() throws IOException {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        StringBuilder sb = new StringBuilder();
        for (; c != 10 && c != 13; c = scan()) {
            sb.append((char) c);
        }
        return sb.toString();
    }
    char nextChar() throws IOException {
        int c;
        for (c = scan(); c <= 32; c = scan()) ;
        return (char) c;
    }
    int nextInt() throws IOException {
        int c, val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+') {
            c = scan();
        }
        for (; c >= '0' && c <= '9'; c = scan()) {
            val = (val << 3) + (val << 1) + (c & 15);
        }
        return neg ? -val : val;
    }
    long nextLong() throws IOException {
        int c;
        long val = 0;
        for (c = scan(); c <= 32; c = scan()) ;
        boolean neg = c == '-';
        if (c == '-' || c == '+') {
            c = scan();
        }
        for (; c >= '0' && c <= '9'; c = scan()) {
            val = (val << 3) + (val << 1) + (c & 15);
        }
        return neg ? -val : val;
    }
}