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.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;
public class C533 {
	
	public static final long p = 1_000_000_007;

	public static void main(String[] args) {
		FastScanner in = new FastScanner(System.in);
		int N = in.nextInt();
		int L = in.nextInt();
		int R = in.nextInt();
		
		int[] countRem = new int[3];
		int[] rem = new int[3];
		int tL = L;
		int tR = R;
		while(tL % 3 != 0) tL--;
		while(tR % 3 != 2) tR++;
		
		int temp = (tR-tL+1) / 3;
		countRem = new int[] {temp, temp, temp};
		while(tL < L) {
			countRem[tL%3]--;
			tL++;
		}
		while(tR > R) {
			countRem[tR % 3]--;
			tR--;
		}
		
		rem[0] = countRem[0];
		rem[1] = countRem[2];
		rem[2] = countRem[1];
		
//		System.out.println("countRem: " + Arrays.toString(countRem));
		
		long[][] dp = new long[N+1][3];
		dp[1][0] = countRem[0];
		dp[1][1] = countRem[1];
		dp[1][2] = countRem[2];
		for(int i = 2; i < dp.length; i++) {
			dp[i][0] = ((dp[i-1][0] * countRem[0]) % p + (dp[i-1][1] * countRem[2]) % p + (dp[i-1][2] * countRem[1]) % p) % p;
			dp[i][1] = ((dp[i-1][0] * countRem[1]) % p + (dp[i-1][1] * countRem[0]) % p + (dp[i-1][2] * countRem[2]) % p) % p;
			dp[i][2] = ((dp[i-1][0] * countRem[2]) % p + (dp[i-1][1] * countRem[1]) % p + (dp[i-1][2] * countRem[0]) % p) % p;
		}
		
/*		System.out.println("dp:");
		for(int i = 0; i < dp.length; i++)
			System.out.println(Arrays.toString(dp[i])); */
		
		System.out.println(dp[N][0]);
	}
	
	/**
	 * Source: Matt Fontaine
	 */
	static class FastScanner {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int chars;

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

		int read() {
			if (chars == -1)
				throw new InputMismatchException();
			if (curChar >= chars) {
				curChar = 0;
				try {
					chars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (chars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		boolean isEndline(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

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

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

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

		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();
		}

		public String nextLine() {
			int c = read();
			while (isEndline(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndline(c));
			return res.toString();
		}
	}

}
/*
2 1 3
outputCopy
3
inputCopy
3 2 2
outputCopy
1
inputCopy
9 9 99
outputCopy
711426616
*/