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.*;

public class Main {
    static Main mm;
    public static void main(String[] args) throws IOException {
        PrintWriter out = new PrintWriter(System.out);
        mm = new Main();
        mm.problemC(new Input(new BufferedReader(new InputStreamReader(System.in))), out);
        out.close();
    }

    static void problemC(Input in, PrintWriter out) throws IOException {
        int n=in.nextInt(),l=in.nextInt(),r=in.nextInt();
        long md=1000000007;
        long[] a=new long[3];
        while(l%3!=0&&l<r){
            a[l%3]++;
            l++;
        }
        while(r%3!=0&&l<r){
            a[r%3]++;
            r--;
        }
        if(l==r)a[l%3]++;
        else{
            a[0]++;
            a[0]+=(r-l)/3;
            a[1]+=(r-l)/3;
            a[2]+=(r-l)/3;
        }
        long[]b=a.clone();
        for (int i = 1; i < n; i++) {
            long[]c=new long[3];
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 3; k++) {
                    c[(j+k)%3]=(c[(j+k)%3]+(a[k]*b[j]%md))%md;
                }
            }
            b[0]=c[0];b[1]=c[1];b[2]=c[2];
        }
        out.println(b[0]);
    }

    static void problemB(Input in, PrintWriter out) throws IOException {
        int n=in.nextInt(),k=in.nextInt();
        int[] s=new int[n+1];
        for (int i = 0; i < n; i++) {
            s[i]=in.nextChar()-'a';
        }
        s[n]=26;
        int[] a=new int[26];
        int m=1;
        for (int i = 0; i < n; i++) {
            if(s[i]==s[i+1])m++;
            else{
                a[s[i]]+=m/k;
                m=1;
            }
        }
        m=0;
        for (int i = 1; i < 26; i++) {
            if(a[i]>a[m])m=i;
        }
        out.println(a[m]);
    }

    static void problemA(Input in, PrintWriter out) throws IOException {
        int n=in.nextInt();
        int[] a=new int[n];
        for (int i = 0; i < n; i++) {
            a[i]=in.nextInt();
        }
        int mn=100000,mi=0;
        for (int i = 2; i < 100; i++) {
            int t=0;
            for (int j = 0; j < n; j++) {
                t+=Math.abs(i-a[j]);
                if(a[j]!=i)t--;
            }
            if(t<mn){mn=t;mi=i;}
        }
        out.println(mi+" "+mn);
    }

    static class Input {
        BufferedReader in;
        StringBuilder sb = new StringBuilder();

        public Input(BufferedReader in) {
            this.in = in;
        }

        public Input(String s) {
            this.in = new BufferedReader(new StringReader(s));
        }

        public String next() throws IOException {
            sb.setLength(0);
            while (true) {
                int c = in.read();
                if (c == -1) {
                    return null;
                }
                if (" \n\r\t".indexOf(c) == -1) {
                    sb.append((char) c);
                    break;
                }
            }
            while (true) {
                int c = in.read();
                if (c == -1 || " \n\r\t".indexOf(c) != -1) {
                    break;
                }
                sb.append((char) c);
            }
            return sb.toString();
        }

        public char nextChar() throws IOException {
            while (true) {
                int c = in.read();
                if (c == -1) {
                    return (char) c;
                }
                if (" \n\r\t".indexOf(c) == -1) {
                    return (char) c;
                }
            }
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
    }
}