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 implements Runnable {

    int maxn = (int)2e5+11;
    int inf = (int)1e9;
    long mod = (long)1e9+7;
    int n,m,k,l,r;
    long memo[][] = new long[maxn][11];
    boolean used[][] = new boolean[maxn][11];

    void solve() throws Exception {
        n = in.iInt();
        l = in.iInt();
        r = in.iInt();
        long ans = calc(1, 0);
        out.println(ans);
    }

    private long calc(int pos, int sum) {
        if (pos>n) {
            if (sum==0) return 1L;
            return 0L;
        }

        if (used[pos][sum]) return memo[pos][sum];
        used[pos][sum] = true;

        long zero = (r-(l-1)+2)/3;
        long one = (r-(l)+2)/3;
        long two = (r-(l+1)+2)/3;

        long ans = 0;
        if (zero>0) {
            ans += calc(pos+1, (sum+l)%3)*zero;
            ans%=mod;
        }
        if (one>0) {
            ans += calc(pos+1, (sum+l+1)%3)*one;
            ans%=mod;
        }
        if (two>0) {
            ans += calc(pos+1, (sum+l+2)%3)*two;
            ans%=mod;
        }

        return memo[pos][sum] = ans;
    }

    class Pair {
        String line;
        int y;

        public Pair(String line, int y) {
            this.line = line;
            this.y = y;
        }
    }

    String fileInName = "";

    static Throwable throwable;
    public static void main (String [] args) throws Throwable {
        Thread thread = new Thread(null, new Main(), "", (1 << 26));
        thread.start();
        thread.join();
        thread.run();
        if (throwable != null)
            throw throwable;
    }

    FastReader in;
    PrintWriter out;

    public void run() {

        try {
            if (!fileInName.isEmpty()) {
                in = new FastReader(new BufferedReader(new FileReader(fileInName+".in")));
                out = new PrintWriter(new BufferedWriter(new FileWriter(fileInName+".out")));
            } else {
                in = new FastReader(new BufferedReader(new InputStreamReader(System.in)));
                out = new PrintWriter(System.out);
            }

            solve();
        } catch(Exception e) {
            throwable = e;
        } finally {
            out.close();
        }

    }

    class FastReader {
        BufferedReader bf;
        StringTokenizer tk = null;

        public FastReader(BufferedReader bf) {
            this.bf = bf;
        }

        public Integer iInt() throws Exception {
            return Integer.parseInt(sString());
        }

        public Long lLong() throws Exception {
            return Long.parseLong(sString());
        }

        public Double dDouble() throws Exception {
            return Double.parseDouble(sString());
        }

        public String sString () throws Exception {
            if (tk==null || !tk.hasMoreTokens()) {
                tk = new StringTokenizer(bf.readLine());
            }
            if (!tk.hasMoreTokens()) return sString();
            else
                return tk.nextToken();
        }
    }
}