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 copy
import itertools
import string

###

def powmod(x, p, m):
	if p <= 0:
		return 1
	if p <= 1:
		return x%m
	return powmod(x*x%m, p//2, m) * (x%m)**(p%2) % m

###

def to_basex(num, x):
	while num > 0:
		yield num % x
		num //= x

def from_basex(it, x):
	ret = 0
	p = 1
	for d in it:
		ret += d*p
		p *= x
	return ret

###

M = 10**9+7

def core():
	n, l, r = (int(x) for x in input().split())
	# print(n, l, r)
	
	l0m3 = (l + 2)//3*3
	r0m3 = r//3*3
	c0m3 = (r0m3 - l0m3)//3 + 1
	c1m3 = c0m3-1 + (1 if l%3 == 1 else 0) + (1 if r%3 != 0 else 0)
	c2m3 = c0m3-1 + (1 if l%3 != 0 else 0) + (1 if r%3 == 2 else 0)
	
	# print(l0m3, r0m3, c0m3, c1m3, c2m3)
	
	dp = [[1], [0], [0]]
	for i in range(n):
		dp[0].append((dp[0][i]*c0m3 + dp[1][i]*c2m3 + dp[2][i]*c1m3) % M)
		dp[1].append((dp[0][i]*c1m3 + dp[1][i]*c0m3 + dp[2][i]*c2m3) % M)
		dp[2].append((dp[0][i]*c2m3 + dp[1][i]*c1m3 + dp[2][i]*c0m3) % M)
		
	# print(dp[0])
	# print(dp[1])
	# print(dp[2])
	
	ans = dp[0][-1]
	print(ans)


core()

































































































