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.util.*;
import java.io.*;
import java.math.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        PrintWriter out = new PrintWriter(System.out);
        //Scanner sc = new Scanner();
        Reader in = new Reader();
        Main solver = new Main();
        solver.solve(out, in);
        out.flush();
        out.close();
 
    }
 
    static int maxn = (int)1e5*2;
    static long mod=(int)1e9+7;
    static int n,t,m,k;
 
    void solve(PrintWriter out, Reader in) throws IOException{   
        n = in.nextInt();
        int l=in.nextInt(),r=in.nextInt();
        
        long dp[][] = new long[n+1][3];
        int a=0,b=0,c=0;
        
        int x=0,y=0;
        if(l%3==2) x=1;
        else if(l%3==1) x=2;
        if(r%3==1) y=1;
        else if(r%3==2) y=2;
        if(r-l+1>=3){
            c = (r-l-x-y)/3+1;
            a = c-1;
            if(l%3==1) a++;
            if(r%3==2|| r%3==1) a++;
            b = c-1;
            if(l%3==1 || l%3==2) b++;
            if(r%3==2) b++;
        }else{
            for(int i=l;i<=r;i++){
                if(i%3==0) c=1;
                if(i%3==1) a=1;
                if(i%3==2) b=1;
            }
        }
        
        dp[1][0]=c;
        dp[1][1]=a;
        dp[1][2]=b;
        
        
        for(int i=2;i<=n;i++){
            dp[i][0] = (dp[i-1][0]*c+dp[i-1][2]*a+dp[i-1][1]*b)%mod;
            dp[i][1] = (dp[i-1][1]*c+dp[i-1][2]*b+dp[i-1][0]*a)%mod;
            dp[i][2] = (dp[i-1][2]*c+dp[i-1][1]*a+dp[i-1][0]*b)%mod;
        }
        
        out.println(dp[n][0]);
        
        
    }
    
    
    static class Edge implements Comparable<Edge> {
        int d,w;
        
        Edge(int d,int w){
            this.d = d;
            this.w = w;
        }
        
        
        public int compareTo(Edge o){
            return this.w - o.w;
        }
    }
    
    
    static class Reader {
 
        private InputStream mIs;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
 
        public Reader() {
            this(System.in);
        }
 
        public Reader(InputStream is) {
            mIs = is;
        }
 
        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
 
        }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = mIs.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }
 
        public String nextLine() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndOfLine(c));
            return res.toString();
        }
 
        public String next() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }
 
        double nextDouble()
        {
            return Double.parseDouble(next());
        }
 
        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 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 boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
 
        public boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }
 
    }
}