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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class SolutionC {

    public static void main(String[] args) throws IOException {
        long base = 1000000007l;
        Reader reader = new Reader();
        long[] params = reader.readLongNumbers();
        long n = params[0];
        long l = params[1];
        long r = params[2];

        long rem0 = 0;
        long rem1 = 0;
        long rem2 = 0;

        if(l % 3 == 1 && l < r) {
            rem1++;
            l++;
        }
        if(l % 3 == 2 && l < r) {
            rem2++;
            l++;
        }
        if(r % 3 == 2 && r > l) {
            rem2++;
            r--;
        }
        if(r % 3 == 1 && r > l) {
            rem1++;
            r--;
        }

        if(r == l) {
            if(l % 3 == 1) {
                rem1++;
            }
            if(l % 3 == 2) {
                rem2++;
            }
            if(l % 3 == 0) {
                rem0++;
            }
        }

        if(r > l) {
            long a = (r - l) / 3;
            rem0 += a + 1;
            rem1 += a;
            rem2 += a;
        }

        long previousZeroRemainder = rem0 % base;
        long previousOneRemainder = rem1 % base;
        long previousTwoRemainder = rem2 % base;

        long newZeroRemainder = rem0 % base;
        long newOneRemainder = 0;
        long newTwoRemainder = 0;

        for(int i = 1; i < n; i++) {
            newZeroRemainder = (previousOneRemainder * rem2) % base + (previousTwoRemainder * rem1) % base +
                    (previousZeroRemainder * rem0) % base;

            newOneRemainder = (previousOneRemainder * rem0) % base + (previousTwoRemainder * rem2) % base +
                    (previousZeroRemainder * rem1) % base;

            newTwoRemainder = (previousOneRemainder * rem1) % base + (previousTwoRemainder * rem0) % base +
                    (previousZeroRemainder * rem2) % base;

            previousZeroRemainder = newZeroRemainder % base;
            previousOneRemainder = newOneRemainder % base;
            previousTwoRemainder = newTwoRemainder % base;

        }
        System.out.println(newZeroRemainder % base);
    }

}





class Reader {

    BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

    public String readStringValue() throws IOException {
        return bufferedReader.readLine();
    }

    public int readIntValue() throws IOException {
        String line = bufferedReader.readLine().replaceAll("\\s+$", "");
        int parsedToInt = Integer.parseInt(line);
        return parsedToInt;
    }

    public int[] readIntNumbers() throws IOException {
        String[] line = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");
        int[] parsedToInt = Arrays.stream(line).mapToInt(Integer::parseInt).toArray();
        return parsedToInt;
    }

    public long readLongValue() throws IOException {
        String line = bufferedReader.readLine().replaceAll("\\s+$", "");
        long parsedToLong = Long.parseLong(line);
        return parsedToLong;
    }

    public long[] readLongNumbers() throws IOException {
        String[] line = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");
        long[] parsedToLong = Arrays.stream(line).mapToLong(Long::parseLong).toArray();
        return parsedToLong;
    }


}