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.*;
import java.lang.*;


public class Main implements Runnable {
    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;
        private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();

            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }

                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }

        public int nextInt() {
            int c = read();

            while (isSpaceChar(c))
                c = read();

            int sgn = 1;

            if (c == '-') {
                sgn = -1;
                c = read();
            }

            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));

            return res * sgn;
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;

            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));
            return res * sgn;
        }

        public double nextDouble() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            double res = 0;
            while (!isSpaceChar(c) && c != '.') {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, nextInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '.') {
                c = read();
                double m = 1;
                while (!isSpaceChar(c)) {
                    if (c == 'e' || c == 'E')
                        return res * Math.pow(10, nextInt());
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }

        public String readString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            }
            while (!isSpaceChar(c));

            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public String next() {
            return readString();
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }

    public static void main(String args[]) throws Exception {
        new Thread(null, new Main(), "Main", 1 << 26).start();
    }

    static long gcd(long a, long b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

    static int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

    static long modPow(long a, long p, long m) {
        if (a == 1) return 1;
        long ans = 1;
        while (p > 0) {
            if (p % 2 == 1) ans = (ans * a) % m;
            a = (a * a) % m;
            p >>= 1;
        }
        return ans;
    }

    static long modInv(long a, long m) {
        return modPow(a, m - 2, m);
    }

    static long sol_x, sol_y, gcd_a_b;

    static void extendedEuclid(long a, long b) {
        if (b == 0) {
            gcd_a_b = a;
            sol_x = 1;
            sol_y = 0;
        } else {
            extendedEuclid(b, a % b);
            long temp = sol_x;
            sol_x = sol_y;
            sol_y = temp - (a / b) * sol_y;
        }
    }

    static class Bhavansort {
        Random random;

        Bhavansort(int a[]) {
            randomArray(a);
            sort(a);
        }

        Bhavansort(long a[]) {
            randomArray(a);
            sort(a);
        }

        static int[] sort(int a[]) {
            Arrays.sort(a);
            return a;
        }

        static long[] sort(long a[]) {
            Arrays.sort(a);
            return a;
        }

        void randomArray(long a[]) {
            int n = a.length;
            for (int i = 0; i < n; i++) {
                int p = random.nextInt(n) % n;
                long tm = a[i];
                a[i] = a[p];
                a[p] = tm;
            }
        }

        void randomArray(int a[]) {
            int n = a.length;
            for (int i = 0; i < n; i++) {
                int p = random.nextInt(n) % n;
                int tm = a[i];
                a[i] = a[p];
                a[p] = tm;
            }
        }
    }


    public static class DJSet {
        public int[] upper;

        public DJSet(int n) {
            upper = new int[n];
            for (int i = 0; i <n ; i++) {
                upper[i]=i;
            }
        }

        public int root(int x) {
            return upper[x] ==x ? x : (upper[x] = root(upper[x]));
        }

        boolean union(int u,int v){
            int ru=root(u);
            int rv=root(v);
            if(ru==rv)return true;
            else{
                if(ru<rv){
                    upper[rv]=ru;
                }
                else{
                    upper[ru]=rv;
                }
                return false;
            }
        }
    }

    ArrayList<Integer> l[];
    int n,child[],visited[];



    public void run() {
        InputReader sc = new InputReader(System.in);
        //Scanner sc=new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int n=sc.nextInt();
        int l=sc.nextInt();
        int r=sc.nextInt();
        int fre[]=new int[3];
        if(r-l+1<100){
            for (int i = l; i <=r ; i++) {
                fre[i%3]++;
            }
        }
        else{
            int i=l;
            while (i%3!=0){
                fre[i%3]++;
                i++;
            }
            int j=r;
            while (j%3!=2){
                fre[j%3]++;
                j--;
            }
            int cc=(j/3)-(i/3)+1;
            fre[0]+=cc;
            fre[1]+=cc;
            fre[2]+=cc;
        }

      //  out.println(fre[0]+" "+fre[1]+" "+fre[2]);

      /*  long dp[][]=new long[n][3];
        dp[0][0]=fre[0];
        long mod=1000000007;
        for (int i = 1; i <n ; i++) {
            for (int j = 0; j <3 ; j++) {
                if(j==0){
                    dp[i][j]=(fre[0]*dp[i-1][0])%mod;
                }
                else if(j==1){
                    dp[i][j]=(dp[i-1][2]*fre[1])%mod;
                }
                else{
                    dp[i][j]=(dp[i-1][1]*fre[2])%mod;
                }
            }
        }

        long sum=0;
        for (int i = 0; i <3 ; i++) {
            sum=(sum+dp[n-1][i])%mod;
        }
        out.println(sum);

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

        long mod=1000000007;

        long dp[][][]=new long[n][3][3];

        dp[0][0][0]=fre[0];
        dp[0][1][1]=fre[1];
        dp[0][2][2]=fre[2];

        for (int i = 1; i <n ; i++) {
            for (int j = 0; j <3 ; j++) {
                for (int k = 0; k <3 ; k++) {
                     if(j==0 && k==0){
                        dp[i][j][k]=((dp[i-1][0][0]+dp[i-1][1][0]+dp[i-1][2][0])*fre[0])%mod;
                    }
                    else if(j==0 && k==1){
                         dp[i][j][k]=((dp[i-1][0][1]+dp[i-1][1][1]+dp[i-1][2][1])*fre[0])%mod;
                    }
                    else if(j==0 && k==2){
                         dp[i][j][k]=((dp[i-1][0][2]+dp[i-1][1][2]+dp[i-1][2][2])*fre[0])%mod;
                    }
                    else if(j==1 && k==0){
                         dp[i][j][k]=((dp[i-1][0][2]+dp[i-1][1][2]+dp[i-1][2][2])*fre[1])%mod;
                    }
                    else if(j==1 && k==1){
                         dp[i][j][k]=((dp[i-1][0][0]+dp[i-1][1][0]+dp[i-1][2][0])*fre[1])%mod;
                    }
                    else if(j==1 && k==2){
                         dp[i][j][k]=((dp[i-1][0][1]+dp[i-1][1][1]+dp[i-1][2][1])*fre[1])%mod;
                    }
                    else if(j==2 && k==0){
                         dp[i][j][k]=((dp[i-1][0][1]+dp[i-1][1][1]+dp[i-1][2][1])*fre[2])%mod;
                    }
                    else if(j==2 && k==1){
                         dp[i][j][k]=((dp[i-1][0][2]+dp[i-1][1][2]+dp[i-1][2][2])*fre[2])%mod;
                    }
                    else if(j==2 && k==2){
                         dp[i][j][k]=((dp[i-1][0][0]+dp[i-1][1][0]+dp[i-1][2][0])*fre[2])%mod;
                    }

                }
            }
        }
        long sum=0;
        for (int i = 0; i <3 ; i++) {

                sum=(sum+dp[n-1][i][0])%mod;

        }

        out.println(sum);

        out.close();


    }





}