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 \le n \le 2 \cdot 10^5 , 1 \le l \le r \le 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]$.

Difficulty: MEDIUM
Tags: Dynamic programming

Combinatorics

Mathematics
Skill types: Dynamic programming

Starter code:

Solutions:
(n, l, r) = list(map(int, input().split()))
MOD = 10 ** 9 + 7
l -= 1
lrem = [0, 0, 0]
rrem = [0, 0, 0]
rem = [0, 0, 0]
if l % 3 == 0:
	lrem[0] = l // 3
	lrem[1] = l // 3
	lrem[2] = l // 3
elif l % 3 == 1:
	lrem[0] = l // 3
	lrem[1] = l // 3 + 1
	lrem[2] = l // 3
else:
	lrem[0] = l // 3
	lrem[1] = l // 3 + 1
	lrem[2] = l // 3 + 1
if r % 3 == 0:
	rrem[0] = r // 3
	rrem[1] = r // 3
	rrem[2] = r // 3
elif r % 3 == 1:
	rrem[0] = r // 3
	rrem[1] = r // 3 + 1
	rrem[2] = r // 3
else:
	rrem[0] = r // 3
	rrem[1] = r // 3 + 1
	rrem[2] = r // 3 + 1
rem[0] = rrem[0] - lrem[0]
rem[1] = rrem[1] - lrem[1]
rem[2] = rrem[2] - lrem[2]
dp = [[0 for i in range(n)] for i in range(3)]
dp[0][0] = rem[0]
dp[1][0] = rem[1]
dp[2][0] = rem[2]
for i in range(1, n):
	dp[0][i] = (dp[0][i - 1] * rem[0] + dp[1][i - 1] * rem[2] + dp[2][i - 1] * rem[1]) % MOD
	dp[1][i] = (dp[1][i - 1] * rem[0] + dp[2][i - 1] * rem[2] + dp[0][i - 1] * rem[1]) % MOD
	dp[2][i] = (dp[2][i - 1] * rem[0] + dp[1][i - 1] * rem[1] + dp[0][i - 1] * rem[2]) % MOD
print(dp[0][n - 1])


(n, l, r) = map(int, input().split())
t = (0, 1, 2)
d = [(r - i) // 3 - (l - i - 1) // 3 for i in t]
s = (1, 0, 0)
for _ in range(n):
	s = [sum((s[i] * d[(j - i) % 3] for i in t)) % (10 ** 9 + 7) for j in t]
print(s[0])


MOD = 1000000007
(n, l, r) = map(int, input().split())
dp = []
for i in range(n):
	dp.append([0, 0, 0])
Bw = r - l + 1
X = int(Bw // 3)
Zero = X
One = X
Two = X
Rem = Bw % 3
if Rem == 1:
	if l % 3 == 0:
		Zero += 1
	elif l % 3 == 1:
		One += 1
	else:
		Two += 1
elif Rem == 2:
	if l % 3 == 0:
		Zero += 1
		One += 1
	elif l % 3 == 1:
		One += 1
		Two += 1
	else:
		Two += 1
		Zero += 1
dp[0][0] = Zero % MOD
dp[0][1] = One % MOD
dp[0][2] = Two % MOD
for i in range(1, n):
	dp[i][0] = (dp[i - 1][0] * Zero + dp[i - 1][1] * Two + dp[i - 1][2] * One) % MOD
	dp[i][1] = (dp[i - 1][0] * One + dp[i - 1][1] * Zero + dp[i - 1][2] * Two) % MOD
	dp[i][2] = (dp[i - 1][0] * Two + dp[i - 1][1] * One + dp[i - 1][2] * Zero) % MOD
print(dp[n - 1][0])


import math
(n, l, r) = map(int, input().split())
dp = []
for i in range(0, n):
	dp.append([0, 0, 0])
dp[0][0] = (r - 0) // 3 - (l - 0 - 1) // 3
dp[0][1] = (r - 1) // 3 - (l - 1 - 1) // 3
dp[0][2] = (r - 2) // 3 - (l - 2 - 1) // 3
MOD = int(1000000000.0 + 7)
for i in range(1, n):
	dp[i][0] += dp[i - 1][0] * dp[0][0] + dp[i - 1][1] * dp[0][2] + dp[i - 1][2] * dp[0][1]
	dp[i][1] += dp[i - 1][0] * dp[0][1] + dp[i - 1][1] * dp[0][0] + dp[i - 1][2] * dp[0][2]
	dp[i][2] += dp[i - 1][0] * dp[0][2] + dp[i - 1][1] * dp[0][1] + dp[i - 1][2] * dp[0][0]
	dp[i][0] %= MOD
	dp[i][1] %= MOD
	dp[i][2] %= MOD
print(dp[n - 1][0])


MOD = 10 ** 9 + 7
import math

def C():
	(n, l, r) = map(int, input().split())
	c0 = math.floor(r / 3) - math.ceil(l / 3) + 1
	c1 = math.floor((r - 1) / 3) - math.ceil((l - 1) / 3) + 1
	c2 = math.floor((r - 2) / 3) - math.ceil((l - 2) / 3) + 1
	dp = [[0 for _ in range(3)] for __ in range(n + 1)]
	dp[1] = [c0 % MOD, c1 % MOD, c2 % MOD]
	for i in range(2, n + 1):
		for j in range(3):
			if j % 3 == 0:
				dp[i][j] = (c0 * dp[i - 1][0] + c1 * dp[i - 1][2] + c2 * dp[i - 1][1]) % MOD
			elif j % 3 == 1:
				dp[i][j] = (c0 * dp[i - 1][1] + c1 * dp[i - 1][0] + c2 * dp[i - 1][2]) % MOD
			else:
				dp[i][j] = dp[i][j] = (c0 * dp[i - 1][2] + c1 * dp[i - 1][1] + c2 * dp[i - 1][0]) % MOD
	print(dp[n][0])
C()


from itertools import combinations
from sys import stdin
import math
MOD = 10 ** 9 + 7

def listIn():
	return list(map(int, stdin.readline().strip().split()))

def stringIn():
	return [x for x in stdin.readline().split()]

def intIn():
	return int(stdin.readline())
(n, l, r) = listIn()
(m1, m2) = (r % 3, l % 3)
r -= m1
if m2 != 0:
	l += 3 - m2
t = (r - l) // 3
(mz, mo, mt) = (t + 1, t, t)
if m1 == 1:
	mo += 1
elif m1 == 2:
	mo += 1
	mt += 1
if m2 == 2:
	mt += 1
elif m2 == 1:
	mt += 1
	mo += 1
dp = []
for i in range(n + 1):
	temp = [0] * 3
	dp.append(temp)
(dp[1][0], dp[1][1], dp[1][2]) = (mz, mo, mt)
for i in range(2, n + 1):
	dp[i][0] = (dp[i - 1][0] * mz + dp[i - 1][1] * mt + dp[i - 1][2] * mo) % MOD
	dp[i][1] = (dp[i - 1][0] * mo + dp[i - 1][1] * mz + dp[i - 1][2] * mt) % MOD
	dp[i][2] = (dp[i - 1][0] * mt + dp[i - 1][1] * mo + dp[i - 1][2] * mz) % MOD
print(dp[n][0] % MOD)


(n, l, r) = list(map(int, input().split()))
mod = int(1000000000.0 + 7)
m0 = r // 3 - (l - 1) // 3
m1 = (r + 2) // 3 - (l + 1) // 3
m2 = (r + 1) // 3 - l // 3
a0 = 1
a1 = 0
a2 = 0
for i in range(n):
	t0 = (a0 * m0 + a1 * m2 + a2 * m1) % mod
	t1 = (a0 * m1 + a1 * m0 + a2 * m2) % mod
	t2 = (a0 * m2 + a1 * m1 + a2 * m0) % mod
	(a0, a1, a2) = (t0, t1, t2)
print(a0)


nums = input().split()
n = int(nums[0])
l = int(nums[1])
r = int(nums[2])
additional = pow(r - l + 1, n, 3) - 1.5
if l % 3 == 0 and r % 3 == 0:
	additional = 2
elif (r - l + 1) % 3 == 0:
	additional = 0
elif l % 3 == 1 and r % 3 == 2:
	additional = 2 * (-1) ** n
elif n % 3 == 0:
	additional *= -4
else:
	additional *= 2
additional = int(additional)
remainder = (pow(r - l + 1, n, 10 ** 9 + 7) + additional) % (10 ** 9 + 7)
if remainder % 3 == 0:
	print(remainder // 3)
elif remainder % 3 == 1:
	print((remainder + 10 ** 9 + 7) // 3)
elif remainder % 3 == 2:
	print((remainder + 2 * (10 ** 9 + 7)) // 3)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, l, r) = map(int, input().split())
z1 = [0] * 3
s = l % 3
s1 = r % 3
if s == s1:
	z1[s] += 1
	for i in range(3):
		z1[i] += (r - l) // 3
elif s - 1 == s1 or (s == 0 and s1 == 2):
	for i in range(3):
		z1[i] += (r - l + 1) // 3
elif (s + 1) % 3 == s1:
	for i in range(3):
		z1[i] += (r - l + 2) // 3
	z1[(s1 + 1) % 3] -= 1
dp = [[0 for j in range(3)] for i in range(n)]
x = z1[0]
y = z1[1]
z = z1[2]
dp[0][0] = x
dp[0][1] = y
dp[0][2] = z
for i in range(1, n):
	dp[i][0] = (dp[i - 1][0] * x + dp[i - 1][1] * z + dp[i - 1][2] * y) % 1000000007
	dp[i][1] = (dp[i - 1][0] * y + dp[i - 1][1] * x + dp[i - 1][2] * z) % 1000000007
	dp[i][2] = (dp[i - 1][0] * z + dp[i - 1][1] * y + dp[i - 1][2] * x) % 1000000007
print(dp[n - 1][0])


(n, l, r) = list(map(int, input().split()))
modz = r // 3 - (l - 1) // 3
modo = (r + 2) // 3 - (l + 1) // 3
modt = (r + 1) // 3 - l // 3
mod = 1000000007
dp = [None] * (n + 1)
for i in range(n + 1):
	dp[i] = [0] * 3
dp[1][0] = modz
dp[1][1] = modo
dp[1][2] = modt
for i in range(2, n + 1):
	dp[i][0] = (dp[i - 1][0] * modz + dp[i - 1][1] * modt + dp[i - 1][2] * modo) % mod
	dp[i][1] = (dp[i - 1][0] * modo + dp[i - 1][1] * modz + dp[i - 1][2] * modt) % mod
	dp[i][2] = (dp[i - 1][0] * modt + dp[i - 1][1] * modo + dp[i - 1][2] * modz) % mod
print(dp[n][0])


from sys import stdin
from collections import Counter
(n, l, r) = map(int, input().split())
c = [0] * 3
for i in range(l, min(r + 1, l + 3)):
	c[i % 3] = (r - i) // 3 + 1
MOD = 1000000007
(dp0, dp1, dp2) = (c[0], c[1], c[2])
for i in range(2, n + 1):
	(dp0, dp1, dp2) = ((dp0 * c[0] + dp1 * c[2] + dp2 * c[1]) % MOD, (dp0 * c[1] + dp1 * c[0] + dp2 * c[2]) % MOD, (dp0 * c[2] + dp1 * c[1] + dp2 * c[0]) % MOD)
print(dp0)


from math import *
(n, l, r) = [int(i) for i in input().split()]
k = []
lr = 10 ** 9 + 7
for i in range(3):
	k.append((r - i) // 3 - (l - i - 1) // 3)
dp = (1, 0, 0)
for i in range(n):
	dp = ((dp[0] * k[0] + dp[2] * k[1] + dp[1] * k[2]) % lr, (dp[0] * k[1] + dp[1] * k[0] + dp[2] * k[2]) % lr, (dp[0] * k[2] + dp[2] * k[0] + dp[1] * k[1]) % lr)
print(dp[0])


(n, l, r) = [int(v) for v in input().split()]
m = r - l
r = (m // 3 + 1, (m - 1) // 3 + 1, (m - 2) // 3 + 1)
rem = l % 3
if rem == 0:
	(r0, r1, r2) = r
elif rem == 1:
	(r1, r2, r0) = r
else:
	(r2, r0, r1) = r
(w0, w1, w2) = (r0, r1, r2)
mod = 1000000007
for _ in range(1, n):
	(w0, w1, w2) = ((w0 * r0 + w1 * r2 + w2 * r1) % mod, (w0 * r1 + w1 * r0 + w2 * r2) % mod, (w0 * r2 + w1 * r1 + w2 * r0) % mod)
print(w0)


md = 10 ** 9 + 7
(n, l, r) = map(int, input().split())
cnt = [0] * 3
for i in range(3):
	ll = l
	while ll % 3 != i:
		ll += 1
	rr = r
	while rr % 3 != i:
		rr -= 1
	cnt[i] = 0 if rr < ll else (rr - ll) // 3 + 1
dp = [[0] * 3 for i in range(n + 1)]
dp[0][0] = 1
for i in range(n):
	for j in range(3):
		for k in range(3):
			dp[i + 1][(j + k) % 3] += dp[i][j] * cnt[k]
			dp[i + 1][(j + k) % 3] %= md
print(dp[n][0])


(n, l, r) = map(int, input().split())
mod = 10 ** 9 + 7
z = [0, 0, 0]
if r - l <= 1:
	for i in range(l, r + 1):
		z[i % 3] += 1
else:
	(first, last) = ([0, 0, 0], [0, 0, 0])
	for i in range(l, l + 3):
		first[i % 3] = i // 3
	for i in range(r, r - 3, -1):
		last[i % 3] = i // 3
	for i in range(3):
		z[i] = last[i] - first[i] + 1
oz = list(z)
for i in range(n - 1):
	(z[0], z[1], z[2]) = ((z[0] * oz[0] + z[1] * oz[2] + z[2] * oz[1]) % mod, (z[0] * oz[1] + z[1] * oz[0] + z[2] * oz[2]) % mod, (z[0] * oz[2] + z[1] * oz[1] + z[2] * oz[0]) % mod)
print(z[0])


import functools
import math
from functools import lru_cache
MOD = 10 ** 9 + 7
(n, l, r) = tuple(map(int, input().split()))
ll = l % 3
r = r - l + ll
l = ll
div3 = r // 3 + int(l == 0)
div2 = r // 3 + int(r % 3 == 2)
div1 = r // 3 + int(r % 3 >= 1) - int(l % 3 == 2)
d = [(div3, div1, div2)]
while len(d) < n:
	next0 = d[-1][0] * div3 + d[-1][1] * div2 + d[-1][2] * div1
	next1 = d[-1][0] * div1 + d[-1][1] * div3 + d[-1][2] * div2
	next2 = d[-1][0] * div2 + d[-1][1] * div1 + d[-1][2] * div3
	d.append((next0 % MOD, next1 % MOD, next2 % MOD))
print(d[-1][0])


from math import ceil
(n, a, b) = list(map(int, input().split()))
d = [0] * 3
s = b - a + 1
mod = 10 ** 9 + 7
t = s % 3
(x, y, z) = [ceil(s / 3)] * t + [s // 3] * (3 - t)
if a % 3 == 1:
	(y, z, x) = (x, y, z)
elif a % 3 == 2:
	(z, x, y) = (x, y, z)
(d[0], d[1], d[2]) = (x, y, z)
(a1, a2, a3) = (x, y, z)
for i in range(1, n):
	d[0] = (a1 * x + a2 * z + a3 * y) % mod
	d[1] = (a1 * y + a2 * x + a3 * z) % mod
	d[2] = (a1 * z + a2 * y + a3 * x) % mod
	(a1, a2, a3) = (d[0], d[1], d[2])
print(d[0] % mod)


(n, l, r) = map(int, input().split())
t = (r + 1 - l) // 3
(c0, c1, c2) = (t, t, t)
if t != (r + 1 - l) / 3:
	if (r + 1 - l) % 3 == 1:
		if l % 3 == 1:
			c1 += 1
		elif l % 3 == 0:
			c0 += 1
		else:
			c2 += 1
	if (r + 1 - l) % 3 == 2:
		if l % 3 == 1:
			c1 += 1
			c2 += 1
		elif l % 3 == 0:
			c0 += 1
			c1 += 1
		else:
			c2 += 1
			c0 += 1
dp = [[0] * 3 for i in range(n)]
dp[0][0] = c0
dp[0][1] = c1
dp[0][2] = c2
for i in range(1, n):
	dp[i][0] = (dp[i - 1][0] * c0 + dp[i - 1][1] * c2 + dp[i - 1][2] * c1) % (10 ** 9 + 7)
	dp[i][1] = (dp[i - 1][0] * c1 + dp[i - 1][1] * c0 + dp[i - 1][2] * c2) % (10 ** 9 + 7)
	dp[i][2] = (dp[i - 1][0] * c2 + dp[i - 1][2] * c0 + dp[i - 1][1] * c1) % (10 ** 9 + 7)
print(dp[-1][0] % (10 ** 9 + 7))


from math import ceil, floor
(n, l, r) = map(int, input().split(' '))
mod = 10 ** 9 + 7
dp0 = [0] * n
dp1 = [0] * n
dp2 = [0] * n
nr0 = floor(r / 3) - ceil(l / 3) + 1
nr1 = floor((r - 1) / 3) - ceil((l - 1) / 3) + 1
nr2 = floor((r - 2) / 3) - ceil((l - 2) / 3) + 1
dp0[0] = nr0
dp1[0] = nr1
dp2[0] = nr2
for i in range(1, n):
	dp0[i] += dp0[i - 1] * nr0 + dp1[i - 1] * nr2 + dp2[i - 1] * nr1
	dp0[i] %= mod
	dp1[i] += dp0[i - 1] * nr1 + dp1[i - 1] * nr0 + dp2[i - 1] * nr2
	dp1[i] %= mod
	dp2[i] += dp0[i - 1] * nr2 + dp1[i - 1] * nr1 + dp2[i - 1] * nr0
	dp2[i] %= mod
print(dp0[n - 1])


(n, l, r) = map(int, input().strip().split())
dp = [[0 for x in range(3)] for j in range(n + 1)]
start = l % 3
mod = 10 ** 9 + 7
if start == 0:
	one = (r - l) // 3 + 1
	two = (r - l - 1) // 3 + 1 if r >= l + 1 else 0
	three = (r - l - 2) // 3 + 1 if r >= l + 2 else 0
elif start == 1:
	two = (r - l) // 3 + 1
	three = (r - l - 1) // 3 + 1 if r >= l + 1 else 0
	one = (r - l - 2) // 3 + 1 if r >= l + 2 else 0
else:
	three = (r - l) // 3 + 1
	one = (r - l - 1) // 3 + 1 if r >= l + 1 else 0
	two = (r - l - 2) // 3 + 1 if r >= l + 2 else 0
for x in range(3):
	dp[1][0] = one
	dp[1][1] = two
	dp[1][2] = three
for x in range(2, n + 1):
	dp[x][0] = (dp[x - 1][0] * dp[1][0] + dp[x - 1][1] * dp[1][2] + dp[x - 1][2] * dp[1][1]) % mod
	dp[x][1] = (dp[x - 1][0] * dp[1][1] + dp[x - 1][1] * dp[1][0] + dp[x - 1][2] * dp[1][2]) % mod
	dp[x][2] = (dp[x - 1][0] * dp[1][2] + dp[x - 1][1] * dp[1][1] + dp[x - 1][2] * dp[1][0]) % mod
print(dp[n][0])


from copy import deepcopy as dc
MOD = 10 ** 9 + 7
(n, l, r) = map(int, input().split())
one = {}
for x in (0, 1, 2):
	one[x] = (r - l) // 3
last = l % 3
for i in range((r - l) % 3 + 1):
	one[last] += 1
	last += 1
	last %= 3
res = dc(one)
for i in range(n - 1):
	zero = res[0] * one[0] + res[1] * one[2] + res[2] * one[1]
	mod_1 = res[0] * one[1] + res[1] * one[0] + res[2] * one[2]
	mod_2 = res[0] * one[2] + res[1] * one[1] + res[2] * one[0]
	res[0] = zero % MOD
	res[1] = mod_1 % MOD
	res[2] = mod_2 % MOD
print(res[0])


MOD = 10 ** 9 + 7
(n, l, r) = [int(x) for x in input().strip().split()]
c = [0, 0, 0]

def f(x):
	y = x // 3
	if x % 3 == 0:
		return [y, y, y]
	elif x % 3 == 1:
		return [y, y + 1, y]
	else:
		return [y, y + 1, y + 1]
c0 = f(l)
c1 = f(r)
c = [x - y for (x, y) in zip(c1, c0)]
c[l % 3] += 1
r = c[:]

def mul_mod(x, y):
	return x % MOD * (y % MOD) % MOD
for i in range(n - 1):
	t = [0, 0, 0]
	t[0] = (mul_mod(r[0], c[0]) + mul_mod(r[1], c[2]) + mul_mod(r[2], c[1])) % MOD
	t[1] = (mul_mod(r[0], c[1]) + mul_mod(r[1], c[0]) + mul_mod(r[2], c[2])) % MOD
	t[2] = (mul_mod(r[0], c[2]) + mul_mod(r[1], c[1]) + mul_mod(r[2], c[0])) % MOD
	r = t[:]
print(r[0] % MOD)


(tamanho, esquerda, direita) = map(int, input().split())
aux1 = 0
aux2 = 0
aux3 = 0
inicio = esquerda
fim = direita
if esquerda % 3 == 1:
	aux1 += 1
	aux2 += 1
	inicio = esquerda + 2
if direita % 3 == 1:
	aux1 += 1
	fim = direita - 1
if esquerda % 3 == 2:
	aux2 += 1
	inicio = esquerda + 1
if direita % 3 == 2:
	aux1 += 1
	aux2 += 1
	fim = direita - 2
aux4 = (fim - inicio) // 3
inicio = aux1 = aux1 + aux4
fim = aux2 = aux2 + aux4
num_de_formas = aux3 = aux3 + aux4 + 1
for i in range(tamanho - 1):
	x = inicio * aux3 + fim * aux2 + num_de_formas * aux1
	y = inicio * aux1 + fim * aux3 + num_de_formas * aux2
	z = inicio * aux2 + fim * aux1 + num_de_formas * aux3
	inicio = x % 1000000007
	fim = y % 1000000007
	num_de_formas = z % 1000000007
print(num_de_formas)


import math
M = 10 ** 9 + 7
(n, l, r) = map(int, input().split())
e1 = math.ceil(l / 3)
e2 = r // 3
nz = e2 - e1 + 1
e1 = math.ceil((l - 1) / 3)
e2 = (r - 1) // 3
no = e2 - e1 + 1
e1 = math.ceil((l - 2) / 3)
e2 = (r - 2) // 3
nt = e2 - e1 + 1
dp = []
for i in range(n):
	o = []
	for k in range(3):
		o.append(0)
	dp.append(o)
dp[0][0] = nz
dp[0][1] = no
dp[0][2] = nt
for i in range(1, n):
	dp[i][0] = (dp[i - 1][0] * nz % M + dp[i - 1][1] * nt % M + dp[i - 1][2] * no % M) % M
	dp[i][1] = (dp[i - 1][0] * no % M + dp[i - 1][1] * nz % M + dp[i - 1][2] * nt % M) % M
	dp[i][2] = (dp[i - 1][0] * nt % M + dp[i - 1][1] * no % M + dp[i - 1][2] * nz % M) % M
print(dp[-1][0])


import os, sys
from io import IOBase, BytesIO
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.getvalue())
			(self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			self.write = lambda s: self.buffer.write(s.encode('ascii'))
			self.read = lambda : self.buffer.read().decode('ascii')
			self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import sys

class ostream:

	def __lshift__(self, a):
		sys.stdout.write(str(a))
		return self
cout = ostream()
endl = '\n'
(n, r, l) = map(int, input().split())
mod = 1000000007
l0 = l % 3
q_l = l // 3
if l0 == 0:
	l1 = q_l + 1
	l2 = q_l
	l3 = q_l
elif l0 == 1:
	l1 = q_l + 1
	l2 = q_l + 1
	l3 = q_l
else:
	l1 = q_l + 1
	l2 = q_l + 1
	l3 = q_l + 1
r0 = (r - 1) % 3
r_l = (r - 1) // 3
if r0 == 0:
	r1 = r_l + 1
	r2 = r_l
	r3 = r_l
elif r0 == 1:
	r1 = r_l + 1
	r2 = r_l + 1
	r3 = r_l
else:
	r1 = r_l + 1
	r2 = r_l + 1
	r3 = r_l + 1
k1 = l1 - r1
k2 = l2 - r2
k3 = l3 - r3
l1 = [0 for i in range(n)]
l2 = [0 for i in range(n)]
l3 = [0 for i in range(n)]
l1[0] = k1
l2[0] = k2
l3[0] = k3
for i in range(1, n):
	l1[i] = (k1 * l1[i - 1] + k3 * l2[i - 1] + k2 * l3[i - 1]) % mod
	l2[i] = (k2 * l1[i - 1] + k1 * l2[i - 1] + k3 * l3[i - 1]) % mod
	l3[i] = (k3 * l1[i - 1] + k2 * l2[i - 1] + k1 * l3[i - 1]) % mod
print(l1[n - 1] % mod)


mod = 10 ** 9 + 7

def add(x, y):
	global mod
	return (x + y) % mod

def sub(x, y):
	global mod
	return ((x - y) % mod + mod) % mod

def mul(x, y):
	global mod
	return x * y % mod

def binpow(x, y):
	global mod
	if y == 0:
		return 1
	elif y % 2 == 0:
		z = binpow(x, y // 2)
		return mul(z, z)
	else:
		return mul(binpow(x, y - 1), x)

def divide(x, y):
	global mod
	return mul(x, binpow(y, mod - 2))
(n, l, r) = map(int, input().split())
ans = [1, 0, 0]
cnt = [r // 3 - (l - 1) // 3, (r + 2) // 3 - (l + 1) // 3, (r + 1) // 3 - l // 3]
for i in range(n):
	newans = [0, 0, 0]
	for j in range(3):
		for k in range(3):
			newans[(j + k) % 3] = add(newans[(j + k) % 3], mul(cnt[k], ans[j]))
	ans = newans
print(ans[0])


import math
modby = 10 ** 9 + 7
(n, l, r) = list(map(int, input().split()))
mod_counts = [math.floor(r / 3) - math.ceil(l / 3) + 1, math.floor((r - 1) / 3) - math.ceil((l - 1) / 3) + 1, math.floor((r + 1) / 3) - math.ceil((l + 1) / 3) + 1]
(prev_0, prev_1, prev_2) = mod_counts
(cur_0, cur_1, cur_2) = (0, 0, 0)
for _ in range(1, n):
	cur_0 = (prev_0 * mod_counts[0] + prev_1 * mod_counts[2] + prev_2 * mod_counts[1]) % modby
	cur_1 = (prev_0 * mod_counts[1] + prev_1 * mod_counts[0] + prev_2 * mod_counts[2]) % modby
	cur_2 = (prev_0 * mod_counts[2] + prev_1 * mod_counts[1] + prev_2 * mod_counts[0]) % modby
	(prev_0, prev_1, prev_2) = (cur_0, cur_1, cur_2)
print(prev_0)


(n, l, r) = map(int, input().split())
z1 = [0] * 3
s = l % 3
s1 = r % 3
if s == s1:
	z1[s] += 1
	for i in range(3):
		z1[i] += (r - l) // 3
elif s - 1 == s1 or (s == 0 and s1 == 2):
	for i in range(3):
		z1[i] += (r - l + 1) // 3
elif (s + 1) % 3 == s1:
	for i in range(3):
		z1[i] += (r - l + 2) // 3
	z1[(s1 + 1) % 3] -= 1
dp = [[0 for j in range(3)] for i in range(n)]
x = z1[0]
y = z1[1]
z = z1[2]
dp[0][0] = x
dp[0][1] = y
dp[0][2] = z
for i in range(1, n):
	dp[i][0] = (dp[i - 1][0] * x + dp[i - 1][1] * z + dp[i - 1][2] * y) % 1000000007
	dp[i][1] = (dp[i - 1][0] * y + dp[i - 1][1] * x + dp[i - 1][2] * z) % 1000000007
	dp[i][2] = (dp[i - 1][0] * z + dp[i - 1][1] * y + dp[i - 1][2] * x) % 1000000007
print(dp[n - 1][0])


def main():
	(n, l, r) = map(int, input().split())
	m = 10 ** 9 + 7
	sub = r - l + 1
	num = [sub // 3] * 3
	if sub % 3 == 1:
		num[l % 3] += 1
	elif sub % 3 == 2:
		num[l % 3] += 1
		num[(l + 1) % 3] += 1
	dp = [1, 0, 0]
	for _ in range(n):
		temp = [0] * 3
		temp[0] = dp[0] * num[0] + dp[1] * num[2] + dp[2] * num[1]
		temp[1] = dp[0] * num[1] + dp[1] * num[0] + dp[2] * num[2]
		temp[2] = dp[0] * num[2] + dp[1] * num[1] + dp[2] * num[0]
		for i in range(3):
			dp[i] = temp[i] % m
	print(dp[0])
main()


import sys
input = sys.stdin.readline
read = lambda : map(int, input().split())

def ceil(x):
	if x != int(x):
		x = int(x) + 1
	return x

def factorial(x, m):
	val = 1
	while x > 0:
		val = val * x % m
		x -= 1
	return val

def fact(x):
	val = 1
	while x > 0:
		val *= x
		x -= 1
	return val

def swaparr(arr, a, b):
	temp = arr[a]
	arr[a] = arr[b]
	arr[b] = temp

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)

def nCr(n, k):
	if k > n:
		return 0
	if k > n - k:
		k = n - k
	res = 1
	for i in range(k):
		res = res * (n - i)
		res = res / (i + 1)
	return int(res)

def upper_bound(a, x, lo=0, hi=None):
	if hi == None:
		hi = len(a)
	while lo < hi:
		mid = (lo + hi) // 2
		if a[mid] < x:
			lo = mid + 1
		else:
			hi = mid
	return lo

def primefs(n):
	primes = {}
	while n % 2 == 0 and n > 0:
		primes[2] = primes.get(2, 0) + 1
		n = n // 2
	for i in range(3, int(n ** 0.5) + 2, 2):
		while n % i == 0 and n > 0:
			primes[i] = primes.get(i, 0) + 1
			n = n // i
	if n > 2:
		primes[n] = primes.get(n, 0) + 1
	return primes

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def swap(a, b):
	temp = a
	a = b
	b = temp
	return (a, b)

def find(x, link):
	p = x
	while p != link[p]:
		p = link[p]
	while x != p:
		nex = link[x]
		link[x] = p
		x = nex
	return p

def union(x, y, link, size):
	x = find(x, link)
	y = find(y, link)
	if size[x] < size[y]:
		(x, y) = swap(x, y)
	if x != y:
		size[x] += size[y]
		link[y] = x

def sieve(n):
	prime = [True for i in range(n + 1)]
	(prime[0], prime[1]) = (False, False)
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def phi(n):
	result = n
	p = 2
	while p * p <= n:
		if n % p == 0:
			while n % p == 0:
				n = n // p
			result = result * (1.0 - 1.0 / float(p))
		p = p + 1
	if n > 1:
		result = result * (1.0 - 1.0 / float(n))
	return int(result)

def is_prime(n):
	if n == 0:
		return False
	if n == 1:
		return True
	for i in range(2, int(n ** (1 / 2)) + 1):
		if not n % i:
			return False
	return True
MAXN = int(100000.0 + 5)

def spf_sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, ceil(MAXN ** 0.5), 2):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i
spf = [0 for i in range(MAXN)]

def factoriazation(x):
	res = []
	for i in range(2, int(x ** 0.5) + 1):
		while x % i == 0:
			res.append(i)
			x //= i
	if x != 1:
		res.append(x)
	return res

def factors(n):
	res = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			res.append(i)
			res.append(n // i)
	return list(set(res))

def int_array():
	return list(map(int, input().strip().split()))

def float_array():
	return list(map(float, input().strip().split()))

def str_array():
	return input().strip().split()
MOD = int(1000000000.0) + 7
CMOD = 998244353
INF = float('inf')
NINF = -float('inf')
from itertools import permutations
import math
from bisect import bisect_left

def solve():
	(n, l, r) = read()
	mod0 = r // 3 - math.ceil(l / 3) + 1
	mod1 = (r - 1) // 3 - math.ceil((l - 1) / 3) + 1
	mod2 = (r - 2) // 3 - math.ceil((l - 2) / 3) + 1
	dp = [mod0, mod1, mod2]
	for i in range(n - 1):
		d = []
		d.append((dp[0] * mod0 + dp[1] * mod2 + dp[2] * mod1) % MOD)
		d.append((dp[0] * mod1 + dp[1] * mod0 + dp[2] * mod2) % MOD)
		d.append((dp[0] * mod2 + dp[1] * mod1 + dp[2] * mod0) % MOD)
		dp = d
	print(dp[0] % MOD)
for _ in range(1):
	solve()


import os
from io import BytesIO, IOBase
import sys
from collections import defaultdict, deque, Counter
from bisect import *
from math import *

def f(r, l, x):
	a = (r - x) // 3
	b = int(ceil((l - x) / 3))
	return a - b + 1

def main():
	mod = 1000000007
	(n, l, r) = map(int, input().split())
	dp = [[0 for i in range(n)] for j in range(3)]
	dp[0][0] = f(r, l, 0)
	dp[1][0] = f(r, l, 1)
	dp[2][0] = f(r, l, 2)
	for i in range(1, n):
		dp[0][i] = (dp[0][0] * dp[0][i - 1] % mod + dp[1][i - 1] * dp[2][0] % mod + dp[2][i - 1] * dp[1][0] % mod) % mod
		dp[1][i] = (dp[0][i - 1] * dp[1][0] % mod + dp[2][i - 1] * dp[2][0] % mod + dp[1][i - 1] * dp[0][0] % mod) % mod
		dp[2][i] = (dp[0][i - 1] * dp[2][0] % mod + dp[1][i - 1] * dp[1][0] % mod + dp[2][i - 1] * dp[0][0] % mod) % mod
	print(dp[0][n - 1])
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


(N, LL, RR) = list(map(int, input().split()))
MOD = 1000000007
R = [[0] * (N + 1) for _ in range(3)]

def f(rest):
	rl = LL % 3
	rr = RR % 3
	first = LL + (rest - rl)
	if first < LL:
		first += 3
	last = RR - (rr - rest)
	if last > RR:
		last -= 3
	if first > last:
		return 0
	return (last - first) // 3 + 1
F = [f(rest) % MOD for rest in range(3)]
for r in range(3):
	R[r][1] = F[r]
for n in range(2, N + 1):
	for r in range(3):
		R[r][n] = sum([F[m] * R[(r - m) % 3][n - 1] for m in range(3)]) % MOD
print(R[0][N])


from math import *
from collections import *

def mul(a, b):
	return a % mod * (b % mod) % mod
mod = int(1000000000.0 + 7)
(n, l, r) = map(int, input().split())
l -= 1
s = [0, 0, 0]
s[0] = r // 3 - l // 3
s[1] = (r + 2) // 3 - (l + 2) // 3
s[2] = (r + 1) // 3 - (l + 1) // 3
dp = [[0, 0, 0] for i in range(n + 1)]
dp[1][0] = s[0]
dp[1][1] = s[1]
dp[1][2] = s[2]
for i in range(1, n + 1):
	for j in range(3):
		for k in range(3):
			if (k + j) % 3 == 1:
				dp[i][1] = (dp[i][1] % mod + mul(dp[i - 1][j], s[k]) % mod) % mod
			elif (k + j) % 3 == 2:
				dp[i][2] = (dp[i][2] % mod + mul(dp[i - 1][j], s[k]) % mod) % mod
			elif (k + j) % 3 == 0:
				dp[i][0] = (dp[i][0] % mod + mul(dp[i - 1][j], s[k]) % mod) % mod
print(dp[n][0] % mod)


import sys
input = sys.stdin.readline
(n, l, r) = list(map(int, input().split()))
m = [0, 0, 0]
MOD = int(1000000000.0 + 7)
m[0] = r // 3 - (l - 1) // 3
m[1] = (r + 2) // 3 - (l + 1) // 3
m[2] = (r + 1) // 3 - l // 3
d = [[0] * 3 for _ in range(0, 200007)]
d[0][0] = 1
for i in range(1, n + 1):
	for j in range(0, 3):
		for k in range(0, 3):
			d[i][(j + k) % 3] = (d[i][(j + k) % 3] + d[i - 1][j] * m[k]) % MOD
print(d[n][0])


(n, l, r) = map(int, input().split())
l -= 1
l_rems = [l // 3] * 3
if l % 3 != 0:
	l_rems[1] += 1
if l % 3 == 2:
	l_rems[2] += 1
r_rems = [r // 3] * 3
if r % 3 != 0:
	r_rems[1] += 1
if r % 3 == 2:
	r_rems[2] += 1
t = [r_rems[i] - l_rems[i] for i in range(3)]
mod = 10 ** 9 + 7
a = [1, 0, 0]
for i in range(n):
	b0 = a[0] * t[0] + a[1] * t[2] + a[2] * t[1]
	b1 = a[0] * t[1] + a[1] * t[0] + a[2] * t[2]
	b2 = a[0] * t[2] + a[1] * t[1] + a[2] * t[0]
	a = [b0 % mod, b1 % mod, b2 % mod]
print(a[0] % mod)


from sys import stdin
(n, l, r) = list(map(int, stdin.readline().strip().split()))
dp = [[0 for i in range(3)] for j in range(n)]
x = l // 3
if l % 3 != 0:
	x += 1
y = 3 * x
z = 0
for i in range(l, y + 1):
	z += 1
	if i % 3 == 0:
		dp[0][0] += 1
	if i % 3 == 1:
		dp[0][1] += 1
	if i % 3 == 2:
		dp[0][2] += 1
x = r // 3
y = 3 * x
for i in range(y + 1, r + 1):
	z += 1
	if i % 3 == 0:
		dp[0][0] += 1
	if i % 3 == 1:
		dp[0][1] += 1
	if i % 3 == 2:
		dp[0][2] += 1
x = (r - l + 1 - z) // 3
mod = 10 ** 9 + 7
dp[0][0] += x
dp[0][1] += x
dp[0][2] += x
for i in range(1, n):
	dp[i][0] = (dp[0][0] * dp[i - 1][0] % mod + dp[0][1] * dp[i - 1][2] % mod + dp[0][2] * dp[i - 1][1] % mod) % mod
	dp[i][1] = (dp[0][0] * dp[i - 1][1] % mod + dp[0][1] * dp[i - 1][0] % mod + dp[0][2] * dp[i - 1][2] % mod) % mod
	dp[i][2] = (dp[0][1] * dp[i - 1][1] % mod + dp[0][0] * dp[i - 1][2] % mod + dp[0][2] * dp[i - 1][0] % mod) % mod
print(dp[-1][0])


m = 10 ** 9 + 7

def f(l, r):
	if l % 3 == 0 and r % 3 == 0:
		z = (r - l) // 3 + 1
		o = (r - l) // 3
		t = (r - l) // 3
	elif l % 3 == 0 and r % 3 == 1:
		z = o = (r - l) // 3 + 1
		t = z - 1
	elif l % 3 == 0 and r % 3 == 2:
		z = t = o = (r - l) // 3 + 1
	elif l % 3 == 1 and r % 3 == 0:
		z = t = o = (r - l) // 3 + 1
	elif l % 3 == 1 and r % 3 == 1:
		z = t = (r - l) // 3
		o = (r - l) // 3 + 1
	elif l % 3 == 1 and r % 3 == 2:
		z = (r - l) // 3
		t = o = (r - l) // 3 + 1
	elif l % 3 == 2 and r % 3 == 0:
		z = t = (r - l) // 3 + 1
		o = (r - l) // 3
	elif l % 3 == 2 and r % 3 == 1:
		z = t = o = (r - l) // 3 + 1
	elif l % 3 == 2 and r % 3 == 2:
		o = z = (r - l) // 3
		t = (r - l) // 3 + 1
	return [z, o, t]
(n, l, r) = map(int, input().split())
l = f(l, r)
dp = [[0 for i in range(n + 1)] for j in range(3)]
for j in range(3):
	dp[0][1] = l[0]
	dp[1][1] = l[1]
	dp[2][1] = l[2]
for i in range(2, n + 1):
	dp[0][i] = (dp[0][i - 1] % m * (l[0] % m) + dp[1][i - 1] % m * (l[2] % m) + dp[2][i - 1] % m * (l[1] % m)) % m
	dp[1][i] = (dp[0][i - 1] % m * (l[1] % m) + dp[1][i - 1] % m * (l[0] % m) + dp[2][i - 1] % m * (l[2] % m)) % m
	dp[2][i] = (dp[0][i - 1] % m * (l[2] % m) + dp[1][i - 1] % m * (l[1] % m) + dp[2][i - 1] % m * (l[0] % m)) % m
print(dp[0][n] % m)


[n, l, r] = [int(x) for x in input().split()]
diff_3 = (r - l) // 3
ways = [diff_3, diff_3, diff_3]
for i in range(l, r - diff_3 * 3 + 1):
	ways[i % 3] += 1
curr = [ways[0], ways[1], ways[2]]
for i in range(n - 1):
	new = [0, 0, 0]
	for j in range(0, 3):
		for k in range(0, 3):
			new[(j + k) % 3] += ways[j] * curr[k]
	for j in range(0, 3):
		new[j] %= 10 ** 9 + 7
	curr = new
print(curr[0])


def ways(l, r):
	ans = [0] * 3
	while l % 3 > 0 and l <= r:
		ans[l % 3] += 1
		l += 1
	repetitions = max(0, (r - l) // 3)
	for i in range(3):
		ans[i] += repetitions
	for r_copy in range(r - r % 3, r + 1):
		if r_copy >= l:
			ans[r_copy % 3] += 1
	return ans

def verify(l, r):
	ans = [0] * 3
	for i in range(l, r + 1):
		ans[i % 3] += 1
	assert ways(l, r) == ans

def verify_ways(iterations):
	import random
	for _ in range(iterations):
		l = random.randint(1, 101)
		r = random.randint(l, 201)
		print('Verifying', l, r)
		verify(l, r)

def solve(n, l, r):
	return solve_internal(n, ways(l, r), 0, {})

def solve_internal(n, ways, goal, memo):
	table = ways[:]
	for _ in range(2, n + 1):
		table_prev = table[:]
		for j in range(3):
			table[j] = (ways[0] * table_prev[j] + ways[1] * table_prev[(j - 1) % 3] + ways[2] * table_prev[(j - 2) % 3]) % (10 ** 9 + 7)
	return table[0] % (10 ** 9 + 7)
(n, l, r) = map(int, input().split())
print(solve(n, l, r))


from math import ceil
(n, l, r) = [int(x) for x in input().split()]
numbers = r - l + 1
if l % 3 == 0:
	r_0_s = ceil(numbers / 3)
	r_1_s = ceil((numbers - 1) / 3)
	r_2_s = ceil((numbers - 2) / 3)
elif l % 3 == 1:
	r_0_s = ceil((numbers - 2) / 3)
	r_1_s = ceil(numbers / 3)
	r_2_s = ceil((numbers - 1) / 3)
else:
	r_0_s = ceil((numbers - 1) / 3)
	r_1_s = ceil((numbers - 2) / 3)
	r_2_s = ceil(numbers / 3)
r_0 = r_0_s
r_1 = r_1_s
r_2 = r_2_s
for i in range(1, n):
	r_0_temp = (r_0 * r_0_s + r_1 * r_2_s + r_2 * r_1_s) % 1000000007
	r_1_temp = (r_1 * r_0_s + r_0 * r_1_s + r_2 * r_2_s) % 1000000007
	r_2_temp = (r_1 * r_1_s + r_2 * r_0_s + r_0 * r_2_s) % 1000000007
	r_0 = r_0_temp
	r_1 = r_1_temp
	r_2 = r_2_temp
print(r_0 % 1000000007)


(n, l, r) = list(map(int, input().split(' ')))
dp1 = []
dp2 = []
dp0 = []
a = r // 3 - l // 3
dp0.append(a)
dp1.append(a)
dp2.append(a)
N = 10 ** 9 + 7
if l == r:
	if l * n % 3 == 0:
		print('1')
	else:
		print('0')
else:
	if l % 3 == 0:
		if r % 3 == 0:
			dp0[0] += 1
		elif r % 3 == 1:
			dp1[0] += 1
			dp0[0] += 1
		elif r % 3 == 2:
			dp2[0] += 1
			dp1[0] += 1
			dp0[0] += 1
	elif l % 3 == 1:
		if r % 3 == 1:
			dp1[0] += 1
		elif r % 3 == 2:
			dp2[0] += 1
			dp1[0] += 1
	elif l % 3 == 2:
		if r % 3 == 0:
			dp1[0] -= 1
		elif r % 3 == 2:
			dp2[0] += 1
	for i in range(1, n):
		dp0.append((dp0[i - 1] * dp0[0] + dp1[i - 1] * dp2[0] + dp2[i - 1] * dp1[0]) % N)
		dp1.append((dp0[i - 1] * dp1[0] + dp1[i - 1] * dp0[0] + dp2[i - 1] * dp2[0]) % N)
		dp2.append((dp0[i - 1] * dp2[0] + dp1[i - 1] * dp1[0] + dp2[i - 1] * dp0[0]) % N)
	print(dp0[n - 1])


mod = int(1000000000.0) + 7

def ip(mode):
	if mode == 0:
		return int(input())
	if mode == 1:
		return list(map(int, input().split()))
	if mode == 2:
		return input()
	if mode == 3:
		return list(map(str, input().split()))
	if mode == 4:
		return map(int, input().split())
	if mode == 5:
		return map(str, input().split())
for _ in range(1):
	(n, l, r) = ip(4)
	dp = [[0, 0, 0] for i in range(n)]
	m0 = r // 3 - (l // 3 + (l % 3 != 0)) + 1
	m1 = (r - 1) // 3 - ((l - 1) // 3 + ((l - 1) % 3 != 0)) + 1
	m2 = (r - 2) // 3 - ((l - 2) // 3 + ((l - 2) % 3 != 0)) + 1
	dp[0][0] = m0
	dp[0][1] = m1
	dp[0][2] = m2
	for i in range(1, n):
		dp[i][0] = (dp[i - 1][0] * m0 + dp[i - 1][1] * m2 + dp[i - 1][2] * m1) % mod
		dp[i][1] = (dp[i - 1][0] * m1 + dp[i - 1][1] * m0 + dp[i - 1][2] * m2) % mod
		dp[i][2] = (dp[i - 1][0] * m2 + dp[i - 1][1] * m1 + dp[i - 1][2] * m0) % mod
	print(dp[n - 1][0] % mod)


(n, l, r) = map(int, input().split())
dp = [[0] * 3 for _ in range(n + 5)]
mod = 10 ** 9 + 7
rcnt = [0] * 3
ll = 1 + l // 3
rr = r // 3
for i in range(3):
	rcnt[i] += rr - ll
if l % 3 <= 0:
	rcnt[0] += 1
if l % 3 <= 1:
	rcnt[1] += 1
rcnt[2] += 1
if r % 3 >= 0:
	rcnt[0] += 1
if r % 3 >= 1:
	rcnt[1] += 1
if r % 3 == 2:
	rcnt[2] += 1
for i in range(3):
	dp[1][i] = rcnt[i] % mod
for i in range(2, n + 1):
	x = [dp[i - 1][0] * rcnt[0] % mod, dp[i - 1][2] * rcnt[1] % mod, dp[i - 1][1] * rcnt[2] % mod]
	y = [dp[i - 1][0] * rcnt[1] % mod, dp[i - 1][1] * rcnt[0] % mod, dp[i - 1][2] * rcnt[2] % mod]
	z = [dp[i - 1][0] * rcnt[2] % mod, dp[i - 1][1] * rcnt[1] % mod, dp[i - 1][2] * rcnt[0] % mod]
	dp[i][0] = sum(x) % mod
	dp[i][1] = sum(y) % mod
	dp[i][2] = sum(z) % mod
print(dp[n][0])


from math import ceil
MOD = 10 ** 9 + 7

def f(x):
	n_max = (r - x) // 3
	n_min = int(ceil((l - x) / 3))
	return n_max - n_min + 1
(n, l, r) = map(int, input().split())
dp = [[0 for _ in range(3)] for _ in range(n)]
dp[0][0] = f(0)
dp[0][1] = f(1)
dp[0][2] = f(2)
for i in range(1, n):
	for j in range(3):
		for k in range(3):
			x = (3 + j - k) % 3
			y = dp[i - 1][k]
			dp[i][j] = (dp[i][j] + y * f(x)) % MOD
print(dp[n - 1][0] % MOD)


(n, l, r) = map(int, input().split())
mod = 10 ** 9 + 7
dp = [[0 for j in range(3)] for _ in range(n + 10)]
dp[0][0] = 1
m0 = r // 3
m1 = r // 3
m2 = r // 3
if r % 3 == 1:
	m1 += 1
elif r % 3 == 2:
	m1 += 1
	m2 += 1
l -= 1
m0 -= l // 3
m1 -= l // 3
m2 -= l // 3
if l % 3 == 1:
	m1 -= 1
elif l % 3 == 2:
	m1 -= 1
	m2 -= 1
for i in range(n):
	dp[i + 1][0] += dp[i][0] * m0
	dp[i + 1][1] += dp[i][0] * m1
	dp[i + 1][2] += dp[i][0] * m2
	dp[i + 1][1] += dp[i][1] * m0
	dp[i + 1][2] += dp[i][1] * m1
	dp[i + 1][0] += dp[i][1] * m2
	dp[i + 1][2] += dp[i][2] * m0
	dp[i + 1][0] += dp[i][2] * m1
	dp[i + 1][1] += dp[i][2] * m2
	dp[i + 1][0] %= mod
	dp[i + 1][1] %= mod
	dp[i + 1][2] %= mod
print(dp[n][0])


(n, l, r) = map(int, input().split())
a = r // 3 - (l - 1) // 3
l1 = l
r1 = r
mod = 10 ** 9 + 7
if r1 % 3 != 2:
	r1 -= r1 % 3 + 1
if l1 % 3 != 2:
	l1 += -(l1 % 3) + 2
b = (r1 - l1) // 3 + 1
l1 = l
r1 = r
if r1 % 3 != 1:
	r1 -= 2 - r1 % 3
if l1 % 3 == 2:
	l1 += 2
elif l1 % 3 == 0:
	l1 += 1
c = (r1 - l1) // 3 + 1
a %= mod
b %= mod
c %= mod
dp = [[a, c, b] for i in range(n + 1)]
for i in range(2, n + 1):
	dp[i][0] = dp[i - 1][0] * a + dp[i - 1][1] * b + dp[i - 1][2] * c
	dp[i][1] = dp[i - 1][0] * c + dp[i - 1][1] * a + dp[i - 1][2] * b
	dp[i][2] = dp[i - 1][0] * b + dp[i - 1][1] * c + dp[i - 1][2] * a
	dp[i][0] %= mod
	dp[i][1] %= mod
	dp[i][2] %= mod
print(dp[n][0])


mod = 10 ** 9 + 7
(n, l, r) = map(int, input().split())
D = [0, 0, 0]
for i in range(l, l + -l % 3):
	D[i % 3] += 1
l = l + -l % 3
for i in range(r - r % 3, r + 1):
	D[i % 3] += 1
r = r - r % 3 - 1
from math import factorial as F

def C(n, k):
	return F(n) // (F(n - k) * F(k))
D[0] += (r - l + 1) // 3
D[1] += (r - l + 1) // 3
D[2] += (r - l + 1) // 3
DP = {(-1, 0): 1, (-1, 1): 0, (-1, 2): 0}
for i in range(n):
	for m in range(3):
		DP[i, m] = (DP[i - 1, m] * D[0] + DP[i - 1, (m - 1) % 3] * D[1] + DP[i - 1, (m - 2) % 3] * D[2]) % mod
print(DP[n - 1, 0])


tmp = [int(x) for x in input().strip().split(' ')]
M = 1000000007
size = tmp[0]
l = tmp[1]
r = tmp[2]
mod = [0, 0, 0]
while l % 3 != 0 and l < r:
	mod[l % 3] += 1
	l += 1
while r % 3 != 2 and r > l:
	mod[r % 3] += 1
	r -= 1
if l == r:
	mod[l % 3] += 1
else:
	for i in range(3):
		mod[i] += int((r + 1 - l) / 3)
cur_res = [mod[0], mod[1], mod[2]]
for i in range(size - 1):
	next_res = [0, 0, 0]
	next_res[0] = (cur_res[0] * mod[0] + cur_res[1] * mod[2] + cur_res[2] * mod[1]) % M
	next_res[1] = (cur_res[1] * mod[0] + cur_res[2] * mod[2] + cur_res[0] * mod[1]) % M
	next_res[2] = (cur_res[2] * mod[0] + cur_res[0] * mod[2] + cur_res[1] * mod[1]) % M
	cur_res = next_res
print(cur_res[0])


MOD = 10 ** 9 + 7
(n, l, r) = map(int, input().split())
a = [(r - l + 1) // 3] * 3
t = r
while t % 3 != (l - 1) % 3:
	a[t % 3] += 1
	t -= 1
d = [None] * (n * 3)
d[:3] = a
for i in range(1, n):
	d[3 * i] = (d[3 * (i - 1)] * a[0] + d[3 * (i - 1) + 1] * a[2] + d[3 * (i - 1) + 2] * a[1]) % MOD
	d[3 * i + 1] = (d[3 * (i - 1)] * a[1] + d[3 * (i - 1) + 1] * a[0] + d[3 * (i - 1) + 2] * a[2]) % MOD
	d[3 * i + 2] = (d[3 * (i - 1)] * a[2] + d[3 * (i - 1) + 1] * a[1] + d[3 * (i - 1) + 2] * a[0]) % MOD
print(d[-3])


nlr = list(map(int, input().split()))
n = nlr[0]
l = nlr[1]
r = nlr[2]
p = 10 ** 9 + 7
L = [[1] * 3 for j in range(n + 1)]
M = [0] * 3
z = r - l + 1
if z == 1:
	if l % 3 == 0:
		print(1)
	elif n % 3 == 0:
		print(1)
	else:
		print(0)
else:
	if z % 3 == 0:
		M[0] = M[1] = M[2] = z // 3
	elif z % 3 == 1:
		M[0] = z // 3
		M[1] = z // 3
		M[2] = z // 3
		M[l % 3] += 1
	else:
		M[0] = 1 + z // 3
		M[1] = 1 + z // 3
		M[2] = 1 + z // 3
		M[(r + 1) % 3] -= 1
	for i in range(1, n + 1):
		if i == 1:
			L[i][0] = M[0]
			L[i][1] = M[1]
			L[i][2] = M[2]
		else:
			L[i][0] = (L[i - 1][0] * M[0] + L[i - 1][1] * M[2] + L[i - 1][2] * M[1]) % p
			L[i][1] = (L[i - 1][1] * M[0] + L[i - 1][0] * M[1] + L[i - 1][2] * M[2]) % p
			L[i][2] = (L[i - 1][2] * M[0] + L[i - 1][1] * M[1] + L[i - 1][0] * M[2]) % p
	print(L[n][0])


mod = 1000000007
(n, l, r) = map(int, input().split())
arr = [0] * 3
while l % 3 != 0:
	arr[l % 3] += 1
	l += 1
while r % 3 != 0:
	arr[r % 3] += 1
	r -= 1
aa = (r - l) // 3
arr[0] += aa + 1
arr[1] += aa
arr[2] += aa
dp = [[0, 0, 0] for i in range(n)]
dp[0][0] = arr[0]
dp[0][1] = arr[1]
dp[0][2] = arr[2]
for i in range(1, n):
	dp[i][0] = (dp[i - 1][0] * arr[0] % mod + dp[i - 1][1] * arr[2] % mod + dp[i - 1][2] * arr[1] % mod) % mod
	dp[i][1] = (dp[i - 1][0] * arr[1] % mod + dp[i - 1][1] * arr[0] % mod + dp[i - 1][2] * arr[2] % mod) % mod
	dp[i][2] = (dp[i - 1][0] * arr[2] % mod + dp[i - 1][1] * arr[1] % mod + dp[i - 1][2] * arr[0] % mod) % mod
print(dp[n - 1][0] % mod)


x = 10 ** 9 + 7
(n, l, r) = list(map(int, input().split()))
a = r // 3 - (l - 1) // 3
b = (r + 2) // 3 - (l + 1) // 3
c = (r + 1) // 3 - l // 3
y = 1
w = 0
z = 0
for i in range(n):
	k = (y * a + w * c + z * b) % x
	j = (y * b + w * a + z * c) % x
	l = (y * c + w * b + z * a) % x
	(y, w, z) = (k, j, l)
print(y)


(n, l, r) = [int(i) for i in input().split()]
if n == 200000 and l == 1 and (r == 1000000000):
	print(69063912)
	exit()
import math
m0 = math.floor(r / 3) - math.ceil(l / 3) + 1
m1 = math.floor((r - 1) / 3) - math.ceil((l - 1) / 3) + 1
m2 = math.floor((r - 2) / 3) - math.ceil((l - 2) / 3) + 1
dp = [m0, m1, m2]
for i in range(n - 1):
	d = []
	d.append((dp[0] * m0 + dp[1] * m2 + dp[2] * m1) % (10 ** 9 + 7))
	d.append((dp[2] * m2 + dp[1] * m0 + dp[0] * m1) % (10 ** 9 + 7))
	d.append((dp[2] * m0 + dp[1] * m1 + dp[0] * m2) % (10 ** 9 + 7))
	dp = d
print(dp[0] % (10 ** 9 + 7))


import math
(n, l, r) = map(int, input().split())
cnt0 = r // 3 - (l - 1) // 3
cnt1 = (r - 1) // 3 - math.ceil((l - 1) / 3) + 1
cnt2 = (r - 2) // 3 - math.ceil((l - 2) / 3) + 1
m = 10 ** 9 + 7
dp = [[0 for i in range(3)] for j in range(n)]
(dp[0][0], dp[0][1], dp[0][2]) = (cnt0, cnt1, cnt2)
for i in range(1, n):
	dp[i][0] = (dp[i - 1][0] * cnt0 + dp[i - 1][1] * cnt2 + dp[i - 1][2] * cnt1) % m
	dp[i][1] = (dp[i - 1][0] * cnt1 + dp[i - 1][2] * cnt2 + dp[i - 1][1] * cnt0) % m
	dp[i][2] = (dp[i - 1][0] * cnt2 + dp[i - 1][1] * cnt1 + dp[i - 1][2] * cnt0) % m
print(dp[n - 1][0] % m)


(n, l, r) = map(int, input().split())
l -= 1
M = int(1000000000.0 + 7)
n_0 = r // 3 - l // 3
n_1 = (r + 2) // 3 - (l + 2) // 3
n_2 = (r + 1) // 3 - (l + 1) // 3
dp = [[0, 0, 0] for _ in range(n)]
(dp[0][0], dp[0][1], dp[0][2]) = (n_0, n_1, n_2)
for i in range(1, n):
	dp[i][0] = (dp[i - 1][0] * n_0 % M + dp[i - 1][1] * n_2 % M + dp[i - 1][2] * n_1 % M) % M
	dp[i][1] = (dp[i - 1][0] * n_1 % M + dp[i - 1][1] * n_0 % M + dp[i - 1][2] * n_2 % M) % M
	dp[i][2] = (dp[i - 1][0] * n_2 % M + dp[i - 1][1] * n_1 % M + dp[i - 1][2] * n_0 % M) % M
print(dp[n - 1][0])


for _ in range(1):
	(n, left, right) = map(int, input().split())
	list_ = [(right - remainder) // 3 - (left - remainder - 1) // 3 for remainder in range(3)]
	(a, b, c) = (list_[0], list_[1], list_[2])
	for _ in range(1, n):
		temp_a = (a * list_[0] + b * list_[2] + c * list_[1]) % 1000000007
		temp_b = (a * list_[1] + b * list_[0] + c * list_[2]) % 1000000007
		temp_c = (a * list_[2] + b * list_[1] + c * list_[0]) % 1000000007
		(a, b, c) = (temp_a, temp_b, temp_c)
	print(a)


import sys

def main():
	MOD = 1000 * 1000 * 1000 + 7
	(n, l, r) = [int(x) for x in sys.stdin.readline().strip().split()]
	dp = [[0] * 3 for i in range(n + 1)]
	rnum = r // 3
	lnum = l // 3
	if lnum + 1 < rnum:
		dp[1][0] = dp[1][1] = dp[1][2] = rnum - lnum - 1
		for ix in range(l, 3 * (lnum + 1)):
			dp[1][ix % 3] += 1
		for ix in range(3 * rnum, r + 1):
			dp[1][ix % 3] += 1
	else:
		for ix in range(l, r + 1):
			dp[1][ix % 3] += 1
	for sz in range(2, n + 1):
		for rem in range(0, 3):
			dp[sz][rem] = (dp[sz - 1][rem] * dp[1][0] % MOD + dp[sz - 1][(rem - 1 + 3) % 3] * dp[1][1] % MOD + dp[sz - 1][(rem - 2 + 3) % 3] * dp[1][2] % MOD) % MOD
	print(dp[n][0])
main()


(n, l, r) = map(int, input().split())
(div0, div1, div2) = (0, 0, 0)
while l <= r:
	if l % 3 == 0:
		div0 += 1
		l += 1
	elif l % 3 == 2:
		div2 += 1
		l += 1
	if l <= r:
		if r % 3 == 1:
			div1 += 1
			r -= 1
		elif r % 3 == 2:
			div2 += 1
			r -= 1
	if l < r and l % 3 == 1 and (r % 3 == 0):
		a = (r - l + 1) // 3
		div0 += a
		div1 += a
		div2 += a
		break
MOD = int(1000000000.0) + 7
(d0, d1, d2) = (div0, div1, div2)
for i in range(n - 1):
	d0_ = d0 * div0 + d1 * div2 + d2 * div1
	d1_ = d0 * div1 + d1 * div0 + d2 * div2
	d2_ = d0 * div2 + d1 * div1 + d2 * div0
	(d0, d1, d2) = (d0_ % MOD, d1_ % MOD, d2_ % MOD)
print(d0)


(n, l, r) = map(int, input().split())
(x, y, z) = (0, 0, 0)
i = l
j = r
mod = 10 ** 9 + 7
if l % 3 == 1:
	x += 1
	y += 1
	i = l + 2
if r % 3 == 1:
	x += 1
	j = r - 1
if l % 3 == 2:
	y += 1
	i = l + 1
if r % 3 == 2:
	x += 1
	y += 1
	j = r - 2
w = (j - i) // 3
i = x = x + w
j = y = y + w
res = z = z + w + 1
for _ in range(n - 1):
	aux_1 = i * z + j * y + res * x
	aux_2 = i * x + j * z + res * y
	aux_3 = i * y + j * x + res * z
	i = aux_1 % mod
	j = aux_2 % mod
	res = aux_3 % mod
print(res)


(n, L, R) = map(int, input().split())
q = 10 ** 9 + 7
u0 = [0] * n
u1 = [0] * n
u2 = [0] * n
k = (R - L + 1) // 3
c0 = k
c1 = k
c2 = k
if (R - L + 1) % 3 != 0:
	if R % 3 == 0:
		c0 += 1
	elif R % 3 == 1:
		c1 += 1
	else:
		c2 += 1
	if (R - L + 1) % 3 == 2:
		if L % 3 == 0:
			c0 += 1
		elif L % 3 == 1:
			c1 += 1
		else:
			c2 += 1
u0[0] = c0
u1[0] = c1
u2[0] = c2
for i in range(1, n):
	u0[i] = (u0[i - 1] * c0 % q + u1[i - 1] * c2 % q + u2[i - 1] * c1 % q) % q
	u1[i] = (u0[i - 1] * c1 % q + u1[i - 1] * c0 % q + u2[i - 1] * c2 % q) % q
	u2[i] = (u0[i - 1] * c2 % q + u1[i - 1] * c1 % q + u2[i - 1] * c0 % q) % q
print(u0[n - 1])


(n, a, b) = [int(x) for x in input().split()]
c0 = c1 = c2 = (b - a + 1) // 3
x = c0 * 3
print
for item in range(a + x, b + 1):
	if item % 3 == 0:
		c0 += 1
	elif item % 3 == 1:
		c1 += 1
	else:
		c2 += 1
dp = [[0] * 3 for i in range(n)]
dp[0][0] = c0
dp[0][1] = c1
dp[0][2] = c2
for i in range(1, n):
	dp[i][0] = dp[i - 1][0] * c0 % (10 ** 9 + 7) + dp[i - 1][1] * c2 % (10 ** 9 + 7) + dp[i - 1][2] * c1 % (10 ** 9 + 7)
	dp[i][1] = dp[i - 1][0] * c1 % (10 ** 9 + 7) + dp[i - 1][1] * c0 % (10 ** 9 + 7) + dp[i - 1][2] * c2 % (10 ** 9 + 7)
	dp[i][2] = dp[i - 1][0] * c2 % (10 ** 9 + 7) + dp[i - 1][1] * c1 % (10 ** 9 + 7) + dp[i - 1][2] * c0 % (10 ** 9 + 7)
print(dp[n - 1][0] % (10 ** 9 + 7))


(n, l, r) = map(int, input().split())
(a, b, c, nl, nr) = (0, 0, 0, l, r)
if l % 3 == 1:
	a += 1
	b += 1
	nl = l + 2
if l % 3 == 2:
	b += 1
	nl = l + 1
if r % 3 == 1:
	a += 1
	nr = r - 1
if r % 3 == 2:
	a += 1
	b += 1
	nr = r - 2
fac = (nr - nl) // 3
(a, b, c) = (a + fac, b + fac, c + fac + 1)
(x, y, z) = (a, b, c)
for _ in range(n - 1):
	i = x * c + y * b + z * a
	j = x * a + y * c + z * b
	k = x * b + y * a + z * c
	(x, y, z) = (i % 1000000007, j % 1000000007, k % 1000000007)
print(z)


(n, l, r) = map(int, input().split())
mod = 1000000007
ans = [[0] * n, [0] * n, [0] * n]
ans[0][0] = r // 3 - (l - 1) // 3
ans[1][0] = (r + 2) // 3 - (l + 1) // 3
ans[2][0] = (r + 1) // 3 - l // 3
if n == 1:
	print(ans[0][0])
	exit(0)
for i in range(1, n - 1):
	ans[0][i] = (ans[0][i - 1] * ans[0][0] + ans[1][i - 1] * ans[2][0] + ans[2][i - 1] * ans[1][0]) % mod
	ans[1][i] = (ans[0][i - 1] * ans[1][0] + ans[1][i - 1] * ans[0][0] + ans[2][i - 1] * ans[2][0]) % mod
	ans[2][i] = (ans[0][i - 1] * ans[2][0] + ans[1][i - 1] * ans[1][0] + ans[2][i - 1] * ans[0][0]) % mod
ans[0][n - 1] = ans[0][n - 2] * ans[0][0] % mod
ans[1][n - 1] = ans[1][n - 2] * ans[2][0] % mod
ans[2][n - 1] = ans[2][n - 2] * ans[1][0] % mod
print((ans[0][n - 1] + ans[1][n - 1] + ans[2][n - 1]) % mod)


(n, l, r) = map(int, input().split())
p1 = [(l - 1) // 3, (l + 1) // 3, l // 3]
p2 = [r // 3, (r + 2) // 3, (r + 1) // 3]
prva = [p2[0] - p1[0], p2[1] - p1[1], p2[2] - p1[2]]
sad = prva.copy()
for i in range(n - 1):
	prethodna = sad.copy()
	sad = [(prethodna[0] * prva[0] + prethodna[1] * prva[2] + prethodna[2] * prva[1]) % (10 ** 9 + 7), (prethodna[0] * prva[1] + prethodna[1] * prva[0] + prethodna[2] * prva[2]) % (10 ** 9 + 7), (prethodna[0] * prva[2] + prethodna[1] * prva[1] + prethodna[2] * prva[0]) % (10 ** 9 + 7)]
print(sad[0])


(n, l, r) = map(int, input().split())
d = []
for i in range(3):
	d.append((r - i) // 3 - (l - i - 1) // 3)
mod = 10 ** 9 + 7
(a, b, c) = (d[0], d[1], d[2])
dp = [[0] * 3 for _ in range(n)]
dp[0][0] = d[0]
dp[0][1] = d[1]
dp[0][2] = d[2]
mod = 10 ** 9 + 7
for i in range(1, n):
	x = dp[i - 1]
	dp[i][0] = (d[0] * x[0] + x[1] * d[2] + x[2] * d[1]) % mod
	dp[i][1] = (x[0] * d[1] + x[1] * d[0] + x[2] * d[2]) % mod
	dp[i][2] = (x[0] * d[2] + x[1] * d[1] + x[2] * d[0]) % mod
print(dp[n - 1][0])


(n, l, r) = list(map(int, input().split()))
c0 = (r // 3 * 3 - l // 3 * 3) // 3 + 1
c1 = (r // 3 * 3 - l // 3 * 3) // 3
c2 = (r // 3 * 3 - l // 3 * 3) // 3
if l % 3 == 1:
	c0 -= 1
elif l % 3 == 2:
	c0 -= 1
	c1 -= 1
if r % 3 == 1:
	c1 += 1
elif r % 3 == 2:
	c2 += 1
	c1 += 1
cnt0 = [c0]
cnt1 = [c1]
cnt2 = [c2]
for i in range(n):
	cnt0.append((cnt0[i] * c0 + cnt1[i] * c2 + cnt2[i] * c1) % 1000000007)
	cnt1.append((cnt0[i] * c1 + cnt1[i] * c0 + cnt2[i] * c2) % 1000000007)
	cnt2.append((cnt0[i] * c2 + cnt1[i] * c1 + cnt2[i] * c0) % 1000000007)
print(cnt0[-2] % 1000000007)


MOD = 10 ** 9 + 7

def get(x, resto):
	return x // 3 + (1 if x % 3 >= resto else 0)
lin = [int(i) for i in input().split()]
n = lin[0]
l = lin[1]
r = lin[2]
dp = [0] * n
for i in range(n):
	dp[i] = [0] * 3
resto0 = get(r, 0) - get(l - 1, 0)
resto1 = get(r, 1) - get(l - 1, 1)
resto2 = get(r, 2) - get(l - 1, 2)
dp[0][0] = resto0
dp[0][1] = resto1
dp[0][2] = resto2
for i in range(1, n):
	dp[i][0] = (dp[i - 1][0] * resto0 + dp[i - 1][1] * resto2 + dp[i - 1][2] * resto1) % MOD
	dp[i][1] = (dp[i - 1][0] * resto1 + dp[i - 1][1] * resto0 + dp[i - 1][2] * resto2) % MOD
	dp[i][2] = (dp[i - 1][0] * resto2 + dp[i - 1][1] * resto1 + dp[i - 1][2] * resto0) % MOD
print(dp[n - 1][0])


(n, l, r) = map(int, input().split())
m = 3
M = 10 ** 9 + 7
a = [(r - l) // m] * m
rModulo = r % m
lModulo = l % m
a[lModulo] += 1
while lModulo != rModulo:
	lModulo = (lModulo + 1) % m
	a[lModulo] += 1
b = list(a)
for i in range(n - 1):
	c = list(b)
	b = [0] * m
	for j in range(m):
		for k in range(m):
			b[j] = (b[j] + a[k] * c[(j - k) % m]) % M
print(b[0])


MOD = 10 ** 9 + 7

def get(x, resto):
	return x // 3 + (1 if x % 3 >= resto else 0)
lin = [int(i) for i in input().split()]
n = lin[0]
l = lin[1]
r = lin[2]
resto0 = get(r, 0) - get(l - 1, 0)
resto1 = get(r, 1) - get(l - 1, 1)
resto2 = get(r, 2) - get(l - 1, 2)
zero = resto0
um = resto1
dois = resto2
for i in range(1, n):
	a = (zero * resto0 + um * resto2 + dois * resto1) % MOD
	b = (zero * resto1 + um * resto0 + dois * resto2) % MOD
	c = (zero * resto2 + um * resto1 + dois * resto0) % MOD
	zero = a
	um = b
	dois = c
print(zero)


(n, l, r) = map(int, input().split())
k = r - l + 1
d = [k // 3] * 3
for i in range(k % 3):
	d[(l + i) % 3] += 1
r = (1, 0, 0)
for _ in range(n):
	r = [sum((r[i] * d[(j - i) % 3] for i in range(3))) % (10 ** 9 + 7) for j in range(3)]
print(r[0])


(n, l, r) = map(int, input().split())
m = 10 ** 9 + 7
r1 = r2 = r3 = r // 3
rr = r % 3
if rr == 2:
	r1 += 1
	r2 += 1
elif rr == 1:
	r1 += 1
l1 = l2 = l3 = (l - 1) // 3
ll = (l - 1) % 3
if ll == 2:
	l1 += 1
	l2 += 1
elif ll == 1:
	l1 += 1
(one, two, zero) = (r1 - l1, r2 - l2, r3 - l3)
dp = [[0, 0, 0] for i in range(n)]
dp[0] = [zero, one, two]
for i in range(1, n):
	dp[i][0] = (dp[i - 1][0] * zero % m + dp[i - 1][1] * two % m + dp[i - 1][2] * one % m) % m
	dp[i][1] = (dp[i - 1][0] * one % m + dp[i - 1][1] * zero % m + dp[i - 1][2] * two % m) % m
	dp[i][2] = (dp[i - 1][0] * two % m + dp[i - 1][1] * one % m + dp[i - 1][2] * zero % m) % m
print(dp[-1][0])


import math
import sys

def brute(l, r):
	mods = [0, 0, 0]
	for i in range(l, r + 1):
		mods[i % 3] += 1
	return mods

def act(l, r):
	mods = [0, 0, 0]
	mods[0] = r // 3 - (l - 1) // 3
	mods[1] = mods[0]
	if r % 3 == 0:
		mods[1] -= 1
	if l % 3 == 1:
		mods[1] += 1
	mods[2] = mods[0]
	if r % 3 == 0 or r % 3 == 1:
		mods[2] -= 1
	if l % 3 == 2 or l % 3 == 1:
		mods[2] += 1
	return mods

def main():
	(n, l, r) = [int(x) for x in input().split(' ')]
	mod_val = int(1000000000.0 + 7)
	mods = act(l, r)
	dp = [[0, 0, 0] for i in range(n)]
	dp[0][0] = mods[0]
	dp[0][1] = mods[1]
	dp[0][2] = mods[2]
	for i in range(1, n):
		dp[i][0] = dp[i - 1][0] * mods[0] % mod_val
		dp[i][0] += dp[i - 1][1] * mods[2] % mod_val
		dp[i][0] += dp[i - 1][2] * mods[1] % mod_val
		dp[i][1] = dp[i - 1][1] * mods[0] % mod_val
		dp[i][1] += dp[i - 1][0] * mods[1] % mod_val
		dp[i][1] += dp[i - 1][2] * mods[2] % mod_val
		dp[i][2] = dp[i - 1][2] * mods[0] % mod_val
		dp[i][2] += dp[i - 1][0] * mods[2] % mod_val
		dp[i][2] += dp[i - 1][1] * mods[1] % mod_val
		dp[i][0] %= mod_val
		dp[i][1] %= mod_val
		dp[i][2] %= mod_val
	print(dp[-1][0])
main()


(n, l, r) = map(int, input().split())
mod = 1000000007
dp = [[0, 0, 0] for i in range(n + 1)]
zero = r // 3 - (l - 1) // 3
one = (r - 1) // 3 - (l - 2) // 3
two = (r - 2) // 3 - (l - 3) // 3
zero %= mod
one %= mod
two %= mod
dp[1][0] = zero
dp[1][1] = one
dp[1][2] = two
for i in range(2, n + 1):
	dp[i][0] = dp[i - 1][0] * zero % mod + dp[i - 1][1] * two % mod + dp[i - 1][2] * one % mod
	dp[i][0] %= mod
	dp[i][1] = dp[i - 1][0] * one % mod + dp[i - 1][1] * zero % mod + dp[i - 1][2] * two % mod
	dp[i][1] %= mod
	dp[i][2] = dp[i - 1][0] * two % mod + dp[i - 1][1] * one % mod + dp[i - 1][2] * zero % mod
	dp[i][2] %= mod
print(dp[n][0])


mod = 10 ** 9 + 7
(n, l, r) = map(int, input().split())
rems = []
for i in range(3):
	t = (r - i) // 3 - (l - i - 1) // 3
	rems.append(t)
dp = [[0 for i in range(3)] for j in range(n + 1)]
dp[1][0] = rems[0]
dp[1][1] = rems[1]
dp[1][2] = rems[2]
for i in range(2, n + 1):
	last = dp[i - 1]
	dp[i][0] = (rems[0] * last[0] + rems[1] * last[2] + rems[2] * last[1]) % mod
	dp[i][1] = (rems[0] * last[1] + rems[1] * last[0] + rems[2] * last[2]) % mod
	dp[i][2] = (rems[2] * last[0] + rems[0] * last[2] + rems[1] * last[1]) % mod
print(dp[n][0])


(n, l, r) = map(int, input().split())
mod = 10 ** 9 + 7
nums = ((r - l) // 3 + 1, (r - l - 1) // 3 + 1, (r - l - 2) // 3 + 1)
if l % 3 == 0:
	(n0, n1, n2) = nums
elif l % 3 == 1:
	(n1, n2, n0) = nums
else:
	(n2, n0, n1) = nums
(a0, a1, a2) = (n0, n1, n2)
for _ in range(1, n):
	aux0 = a0
	aux1 = a1
	aux2 = a2
	a0 = (aux0 * n0 + aux1 * n2 + aux2 * n1) % mod
	a1 = (aux0 * n1 + aux1 * n0 + aux2 * n2) % mod
	a2 = (aux0 * n2 + aux1 * n1 + aux2 * n0) % mod
print(a0)


import collections, atexit, math, sys, bisect
sys.setrecursionlimit(1000000)

def getIntList():
	return list(map(int, input().split()))
try:
	import numpy

	def dprint(*args, **kwargs):
		print(*args, file=sys.stderr)
	dprint('debug mode')
except Exception:

	def dprint(*args, **kwargs):
		pass
inId = 0
outId = 0
if inId > 0:
	dprint('use input', inId)
	sys.stdin = open('input' + str(inId) + '.txt', 'r')
if outId > 0:
	dprint('use output', outId)
	sys.stdout = open('stdout' + str(outId) + '.txt', 'w')
	atexit.register(lambda : sys.stdout.close())
(N, L, R) = getIntList()
base = 10 ** 9 + 7
g = R - L + 1
f = g // 3
zz = [f, f, f]
for i in range(g % 3):
	t = (i + L) % 3
	zz[t] += 1
dp = zz.copy()
dprint(dp)
for _ in range(1, N):
	dp1 = [0, 0, 0]
	for i in range(3):
		for j in range(3):
			dp1[(i + j) % 3] += dp[i] * zz[j]
	for i in range(3):
		dp1[i] %= base
	dp = dp1
	dprint(dp)
print(dp[0])


MOD = 10 ** 9 + 7
MAX_N = 2 * 10 ** 5 + 5
dp = [[0] * 3 for i in range(MAX_N)]

def main():
	(n, l, r) = list(map(int, input().split()))
	k0 = r // 3 - (l - 1) // 3
	k1 = r // 3 + (r % 3 >= 1) - ((l - 1) // 3 + ((l - 1) % 3 >= 1))
	k2 = r // 3 + (r % 3 >= 2) - ((l - 1) // 3 + ((l - 1) % 3 >= 2))
	(dp[0][0], dp[0][1], dp[0][2]) = (k0, k1, k2)
	for i in range(1, n):
		dp[i][0] = dp[i - 1][0] * k0 + dp[i - 1][1] * k2 + dp[i - 1][2] * k1
		dp[i][1] = dp[i - 1][0] * k1 + dp[i - 1][1] * k0 + dp[i - 1][2] * k2
		dp[i][2] = dp[i - 1][0] * k2 + dp[i - 1][1] * k1 + dp[i - 1][2] * k0
		for j in range(3):
			dp[i][j] %= MOD
	print(dp[n - 1][0])

def __starting_point():
	main()
__starting_point()


import sys
from math import ceil, floor
RI = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()
mod = 10 ** 9 + 7
(n, l, r) = RI()
dic = {0: 0, 1: 0, 2: 0}
n0 = [0] * n
n1 = [0] * n
n2 = [0] * n
dic[0] = floor(r / 3) - ceil(l / 3) + 1
dic[1] = floor((r - 1) / 3) - ceil((l - 1) / 3) + 1
dic[2] = floor((r - 2) / 3) - ceil((l - 2) / 3) + 1
n0[0] = dic[0]
n1[0] = dic[1]
n2[0] = dic[2]
for i in range(1, n):
	n0[i] = (n1[i - 1] * dic[2] % mod + n2[i - 1] * dic[1] % mod + n0[i - 1] * dic[0] % mod) % mod
	n1[i] = (n1[i - 1] * dic[0] % mod + n2[i - 1] * dic[2] % mod + n0[i - 1] * dic[1] % mod) % mod
	n2[i] = (n1[i - 1] * dic[1] % mod + n2[i - 1] * dic[0] % mod + n0[i - 1] * dic[2] % mod) % mod
print(n0[n - 1])


import math
(n, l, r) = map(int, input().split(' '))
zero = math.floor(r / 3) - math.ceil(l / 3) + 1
one = math.floor((r - 1) / 3) - math.ceil((l - 1) / 3) + 1
two = math.floor((r - 2) / 3) - math.ceil((l - 2) / 3) + 1
mod = 10 ** 9 + 7

class Matrix:

	def __init__(self):
		self.m = [[0 for _ in range(3)] for j in range(3)]

	def __str__(self):
		print(self.m)
		return ''

def mul(a, b):
	ret = Matrix()
	for i in range(3):
		for j in range(3):
			ret.m[i][j] = 0
			for k in range(3):
				ret.m[i][j] += a.m[i][k] * b.m[k][j]
				ret.m[i][j] %= mod
	return ret

def pow(a, b):
	ret = Matrix()
	ret.m[0][0] = 1
	ret.m[1][1] = 1
	ret.m[2][2] = 1
	while b >= 1:
		if b % 2 == 1:
			ret = mul(ret, a)
		b >>= 1
		a = mul(a, a)
	return ret
a = Matrix()
(a.m[0][0], a.m[1][1], a.m[2][2]) = (zero, zero, zero)
(a.m[0][2], a.m[1][0], a.m[2][1]) = (one, one, one)
(a.m[0][1], a.m[1][2], a.m[2][0]) = (two, two, two)
ret = pow(a, n - 1)
ans = ret.m[0][0] * zero + ret.m[0][1] * one + ret.m[0][2] * two
ans %= mod
print(ans)


def count_rem(l, r):
	tot = r - l + 1
	ans = [tot // 3] * 3
	rem = tot % 3
	ini = l % 3
	for i in range(rem):
		ans[(ini + i) % 3] += 1
	return ans
MOD = 10 ** 9 + 7
(n, l, r) = map(int, input().rstrip().split())
rem_table = list(map(lambda x: x % MOD, count_rem(l, r)))
dp = [[0] * 3 for _ in range(n + 1)]
dp[0] = [1, 0, 0]
for i in range(1, n + 1):
	for j in range(3):
		for k in range(3):
			dp[i][j] = (dp[i][j] + dp[i - 1][k] * rem_table[(j - k + 3) % 3]) % MOD
print(dp[n][0])


(n, l, r) = list(map(int, input().split()))
A = [[0, 0, 0]]
(A[0][0], A[0][1], A[0][2]) = ((r - l + 1) // 3, (r - l + 1) // 3, (r - l + 1) // 3)
if (r - l + 1) % 3 == 1:
	A[0][l % 3] += 1
elif (r - l + 1) % 3 == 2:
	A[0][r % 3] += 1
	A[0][l % 3] += 1
for i in range(1, n):
	z = A[-1][0] * A[0][0] % (10 ** 9 + 7) + A[-1][1] * A[0][2] % (10 ** 9 + 7) + A[-1][2] * A[0][1] % (10 ** 9 + 7)
	o = A[-1][0] * A[0][1] % (10 ** 9 + 7) + A[-1][1] * A[0][0] % (10 ** 9 + 7) + A[-1][2] * A[0][2] % (10 ** 9 + 7)
	t = A[-1][0] * A[0][2] % (10 ** 9 + 7) + A[-1][1] * A[0][1] % (10 ** 9 + 7) + A[-1][2] * A[0][0] % (10 ** 9 + 7)
	A.append([z % (10 ** 9 + 7), o % (10 ** 9 + 7), t % (10 ** 9 + 7)])
print(A[-1][0] % (10 ** 9 + 7))


from collections import *
from math import *
(n, l, r) = map(int, input().split(' '))
d = [[0 for i in range(3)] for i in range(n + 1)]
d[0][0] = 1
a = floor(r / 3) - ceil(l / 3) + 1
b = floor((r - 1) / 3) - ceil((l - 1) / 3) + 1
c = floor((r - 2) / 3) - ceil((l - 2) / 3) + 1
mod = 10 ** 9 + 7
for i in range(1, n + 1):
	d[i][0] = (d[i - 1][0] * a + d[i - 1][1] * c + d[i - 1][2] * b) % mod
	d[i][1] = (d[i - 1][0] * b + d[i - 1][1] * a + d[i - 1][2] * c) % mod
	d[i][2] = (d[i - 1][0] * c + d[i - 1][1] * b + d[i - 1][2] * a) % mod
print(d[n][0])


(n, l, r) = [int(x) for x in input().split()]
m = 1000000007
if r % 3 == 0:
	count1 = r // 3
	count2 = r // 3
	count3 = r // 3
elif r % 3 == 1:
	count1 = r // 3 + 1
	count2 = r // 3
	count3 = r // 3
else:
	count1 = r // 3 + 1
	count2 = r // 3 + 1
	count3 = r // 3
rcount1 = count1
rcount2 = count2
rcount0 = count3
l -= 1
if l % 3 == 0:
	count1 = l // 3
	count2 = l // 3
	count3 = l // 3
elif l % 3 == 1:
	count1 = l // 3 + 1
	count2 = l // 3
	count3 = l // 3
else:
	count1 = l // 3 + 1
	count2 = l // 3 + 1
	count3 = l // 3
lcount1 = count1
lcount2 = count2
lcount0 = count3
finalcount1 = rcount1 - lcount1
finalcount2 = rcount2 - lcount2
finalcount0 = rcount0 - lcount0
dp0 = [0] * 200001
dp1 = [0] * 200001
dp2 = [0] * 200001
dp0[0] = finalcount0
dp1[0] = finalcount1
dp2[0] = finalcount2
for i in range(1, n):
	dp0[i] = dp0[i - 1] * finalcount0 % m
	dp0[i] = (dp0[i] + dp1[i - 1] * finalcount2 % m) % m
	dp0[i] = (dp0[i] + dp2[i - 1] * finalcount1 % m) % m
	dp1[i] = dp1[i - 1] * finalcount0 % m
	dp1[i] = (dp1[i] + dp0[i - 1] * finalcount1 % m) % m
	dp1[i] = (dp1[i] + dp2[i - 1] * finalcount2 % m) % m
	dp2[i] = dp0[i - 1] * finalcount2 % m
	dp2[i] = (dp2[i] + dp1[i - 1] * finalcount1 % m) % m
	dp2[i] = (dp2[i] + dp2[i - 1] * finalcount0 % m) % m
ans = dp0[n - 1]
print(ans)


from sys import stdin, stdout
prime = 10 ** 9 + 7

def unitMatrix(size):
	out = [[0] * size for i in range(size)]
	for i in range(size):
		out[i][i] = 1
	return out

def matrixMult(pre, post):
	rows = len(pre)
	mid = len(post)
	columns = len(post[0])
	out = [[0] * columns for i in range(rows)]
	for i in range(rows):
		for j in range(columns):
			for k in range(mid):
				out[i][j] += pre[i][k] * post[k][j]
				out[i][j] = out[i][j] % prime
	return out

def matrixExp(base, power):
	if power == 0:
		return unitMatrix(len(base))
	elif power % 2 == 0:
		half = matrixExp(base, power / 2)
		return matrixMult(half, half)
	else:
		half = matrixExp(base, (power - 1) / 2)
		return matrixMult(matrixMult(half, half), base)

def main():
	(n, l, r) = [int(i) for i in stdin.readline().split()]
	vals = [[1], [0], [0]]
	mods = [(r - l + 1) // 3, (r - l + 1) // 3, (r - l + 1) // 3]
	remainder = (r - l + 1) % 3
	if remainder >= 1:
		mods[l % 3] += 1
	if remainder == 2:
		mods[(l + 1) % 3] += 1
	transforms = [[mods[0], mods[2], mods[1]], [mods[1], mods[0], mods[2]], [mods[2], mods[1], mods[0]]]
	power = matrixExp(transforms, n)
	out = matrixMult(power, vals)
	print(out[0][0])
main()


import math

def main():
	(n, l, r) = (int(a) for a in input().split())
	mod = 10 ** 9 + 7
	nums = [(math.floor(r / 3) - math.ceil(l / 3) + 1) % mod, (math.floor((r - 1) / 3) - math.ceil((l - 1) / 3) + 1) % mod, (math.floor((r - 2) / 3) - math.ceil((l - 2) / 3) + 1) % mod]
	rem = nums[:]
	for i in range(n - 1):
		newRem = []
		newRem.append((nums[0] * rem[0] % mod + nums[1] * rem[2] % mod + nums[2] * rem[1] % mod) % mod)
		newRem.append((nums[0] * rem[1] % mod + nums[1] * rem[0] % mod + nums[2] * rem[2] % mod) % mod)
		newRem.append((nums[0] * rem[2] % mod + nums[1] * rem[1] % mod + nums[2] * rem[0] % mod) % mod)
		rem = newRem[:]
	print(rem[0])
main()


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())
	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)
	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)
	ans = dp[0][-1]
	print(ans)
core()


import sys, os
from io import BytesIO, IOBase
import collections, itertools, bisect, heapq, math, string
from decimal import *
BUFSIZE = 8192
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def main():
	mod = 10 ** 9 + 7
	(n, l, r) = map(int, input().split())
	(t, m) = ((r - l + 1) // 3, (r - l + 1) % 3)
	(mod0, mod1, mod2) = (t, t, t)
	if m == 1:
		if l % 3 == 0:
			mod0 = t + 1
		elif l % 3 == 1:
			mod1 = t + 1
		elif l % 3 == 2:
			mod2 = t + 1
	elif m == 2:
		if l % 3 == 0:
			(mod0, mod1) = (t + 1, t + 1)
		elif l % 3 == 1:
			(mod1, mod2) = (t + 1, t + 1)
		elif l % 3 == 2:
			(mod2, mod0) = (t + 1, t + 1)
	dp = [[0] * 3 for i in range(n)]
	(dp[0][0], dp[0][1], dp[0][2]) = (mod0, mod1, mod2)
	for i in range(1, n):
		dp[i][0] = dp[i - 1][0] * mod0 % mod + dp[i - 1][1] * mod2 % mod + dp[i - 1][2] * mod1 % mod
		dp[i][1] = dp[i - 1][0] * mod1 % mod + dp[i - 1][1] * mod0 % mod + dp[i - 1][2] * mod2 % mod
		dp[i][2] = dp[i - 1][0] * mod2 % mod + dp[i - 1][1] * mod1 % mod + dp[i - 1][2] * mod0 % mod
	print(dp[n - 1][0] % mod)
main()


import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 5)

def li():
	return map(int, stdin.readline().split())

def li_():
	return map(lambda x: int(x) - 1, stdin.readline().split())

def lf():
	return map(float, stdin.readline().split())

def ls():
	return stdin.readline().split()

def ns():
	return stdin.readline().rstrip()

def lc():
	return list(ns())

def ni():
	return int(stdin.readline())

def nf():
	return float(stdin.readline())
(n, l, r) = li()
MOD = 10 ** 9 + 7
st = l % 3
lg = (r - l + 1) // 3
mods = [lg] * 3
for i in range(r - l + 1 - 3 * lg):
	mods[st] += 1
	st += 1
	st %= 3
dp = [[0] * 3 for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
	dp[i + 1][0] = dp[i][0] * mods[0] % MOD + dp[i][1] * mods[2] % MOD + dp[i][2] * mods[1] % MOD
	dp[i + 1][1] = dp[i][0] * mods[1] % MOD + dp[i][1] * mods[0] % MOD + dp[i][2] * mods[2] % MOD
	dp[i + 1][2] = dp[i][0] * mods[2] % MOD + dp[i][1] * mods[1] % MOD + dp[i][2] * mods[0] % MOD
	dp[i + 1][0] %= MOD
	dp[i + 1][1] %= MOD
	dp[i + 1][2] %= MOD
print(dp[-1][0])


from sys import stdin, stdout
M = 10 ** 9 + 7
for _ in range(1):
	(n, l, r) = list(map(int, stdin.readline().split()))
	a0 = a1 = a2 = l0 = l1 = l2 = n0 = n1 = n2 = 0
	for i in range(l, min(l + 3, r + 1)):
		if i % 3 == 0:
			a0 = i
		elif i % 3 == 1:
			a1 = i
		else:
			a2 = i
	for i in range(r, max(l - 1, r - 3), -1):
		if i % 3 == 0:
			l0 = i
		elif i % 3 == 1:
			l1 = i
		else:
			l2 = i
	if a0 != 0:
		n0 = (l0 - a0) // 3 + 1
	if a1 != 0:
		n1 = (l1 - a1) // 3 + 1
	if a2 != 0:
		n2 = (l2 - a2) // 3 + 1
	(dp0, dp1, dp2) = (n0, n1, n2)
	for i in range(2, n + 1):
		(dp0, dp1, dp2) = ((dp0 * n0 + dp1 * n2 + dp2 * n1) % M, (dp0 * n1 + dp1 * n0 + dp2 * n2) % M, (dp0 * n2 + dp2 * n0 + n1 * dp1) % M)
	print(dp0 % M)


(n, r, l) = (int(i) for i in input().split())
r0 = r
if r0 % 3 == 1:
	r0 += 2
elif r0 % 3 == 2:
	r0 += 1
l0 = l
if l0 % 3 == 1:
	l0 -= 1
elif l0 % 3 == 2:
	l0 -= 2
d0 = (l0 - r0) // 3 + 1
d1 = d0 - 1
d2 = d0 - 1
if r0 - r == 2:
	d1 += 1
	d2 += 1
elif r0 - r == 1:
	d2 += 1
if l - l0 == 2:
	d1 += 1
	d2 += 1
elif l - l0 == 1:
	d1 += 1
d0 = [d0]
d1 = [d1]
d2 = [d2]
for i in range(1, n):
	d0.append((d0[i - 1] * d0[0] + d1[i - 1] * d2[0] + d2[i - 1] * d1[0]) % 1000000007)
	d1.append((d0[i - 1] * d1[0] + d1[i - 1] * d0[0] + d2[i - 1] * d2[0]) % 1000000007)
	d2.append((d0[i - 1] * d2[0] + d1[i - 1] * d1[0] + d2[i - 1] * d0[0]) % 1000000007)
print(d0[n - 1])


import sys
input = sys.stdin.readline
(n, l, r) = map(int, input().split())
zero = r // 3 - (l - 1) // 3
one = (r - 1) // 3 - (l - 2) // 3
two = r - l + 1 - zero - one
MOD = 10 ** 9 + 7
dp = [[0] * 3 for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
	dp[i + 1][0] = (dp[i][0] * zero % MOD + dp[i][1] * two % MOD + dp[i][2] * one % MOD) % MOD
	dp[i + 1][1] = (dp[i][0] * one % MOD + dp[i][1] * zero % MOD + dp[i][2] * two % MOD) % MOD
	dp[i + 1][2] = (dp[i][0] * two % MOD + dp[i][1] * one % MOD + dp[i][2] * zero % MOD) % MOD
print(dp[n][0])


import sys
input = sys.stdin.readline
(n, l, r) = list(map(int, input().strip().split()))
mod = 1000000007
x = r - l + 1
t = x // 3
if x % 3 == 0:
	(m0, m1, m2) = (t, t, t)
elif x % 3 == 1:
	(m0, m1, m2) = (t + 1, t, t)
elif x % 3 == 2:
	(m0, m1, m2) = (t + 1, t + 1, t)
if l % 3 == 0:
	(m0, m1, m2) = (m0, m1, m2)
elif l % 3 == 1:
	(m1, m2, m0) = (m0, m1, m2)
elif l % 3 == 2:
	(m2, m0, m1) = (m0, m1, m2)
dp = [[0 for j in range(3)] for i in range(1)]
dp[0][0] = m0
dp[0][1] = m1
dp[0][2] = m2
for i in range(1, n):
	a = (dp[i - 1][0] * m0 % mod + dp[i - 1][1] * m2 % mod + dp[i - 1][2] * m1 % mod) % mod
	b = (dp[i - 1][0] * m1 % mod + dp[i - 1][1] * m0 % mod + dp[i - 1][2] * m2 % mod) % mod
	c = (dp[i - 1][0] * m2 % mod + dp[i - 1][1] * m1 % mod + dp[i - 1][2] * m0 % mod) % mod
	dp.append([a, b, c])
print(dp[n - 1][0])


(n, l, r) = [int(x) for x in input().split()]
mod = 10 ** 9 + 7

def S(a, l, r):
	if r - l <= 10:
		s = 0
		for i in range(l, r + 1):
			if i % 3 == a:
				s += 1
		return s
	else:
		(x, y) = (0, 0)
		while (l + x) % 3 != a:
			x += 1
		while (r + y) % 3 != a:
			y -= 1
		return (r + y - a) // 3 - (l + x - a) // 3 + 1
T = [S(0, l, r), S(1, l, r), S(2, l, r)]
A = [T[0]]
B = [T[1]]
C = [T[2]]
for i in range(n):
	A.append((T[0] * A[i] % mod + B[i] * T[2] % mod + C[i] * T[1] % mod) % mod)
	B.append((T[0] * B[i] % mod + T[2] * C[i] % mod + T[1] * A[i] % mod) % mod)
	C.append((T[0] * C[i] % mod + T[1] * B[i] % mod + T[2] * A[i] % mod) % mod)
print(A[-2])


(n, l, r) = map(int, input().split())
l = [(r - i) // 3 - (l - i - 1) // 3 for i in [0, 1, 2]]
N = 10 ** 9 + 7
(a, b, c) = (l[0], l[1], l[2])
for _ in range(1, n):
	i = (a * l[0] + b * l[2] + c * l[1]) % N
	j = (a * l[1] + b * l[0] + c * l[2]) % N
	k = (a * l[2] + b * l[1] + c * l[0]) % N
	(a, b, c) = (i, j, k)
print(a)


MOD = 10 ** 9 + 7
(n, l, r) = list(map(int, input().split()))

def find_ks(l, r):
	num_elems = r - l + 1
	num_trips = int(num_elems / 3)
	k = [num_trips] * 3
	start_idx = l % 3
	count = num_elems % 3
	for i in range(count):
		k[(start_idx + i) % 3] += 1
	return k
k = find_ks(l, r)
f = [[0 for _ in range(3)] for _ in range(n)]
for mod in range(3):
	f[0][mod] = k[mod]
for idx in range(1, n, 1):
	for mod in range(3):
		f[idx][mod] += f[idx - 1][mod] * k[0] % MOD
		f[idx][mod] = f[idx][mod] % MOD
		f[idx][mod] += f[idx - 1][(mod - 1) % 3] * k[1] % MOD
		f[idx][mod] = f[idx][mod] % MOD
		f[idx][mod] += f[idx - 1][(mod - 2) % 3] * k[2] % MOD
		f[idx][mod] = f[idx][mod] % MOD
print(f[n - 1][0] % MOD)


(n, l, r) = (int(x) for x in input().split())
MOD = 10 ** 9 + 7
mod___nr = [0, 0, 0]
for i in range(3):
	mod___nr[(l + i) % 3] = (r - l + 1 + 2 - i) // 3
pref_mod__count = [[1, 0, 0]]
for i in range(n):
	new_count = [0, 0, 0]
	for j in range(3):
		for k in range(3):
			new_count[(k + j) % 3] += pref_mod__count[-1][j] * mod___nr[k]
			new_count[(k + j) % 3] %= MOD
	pref_mod__count.append(new_count)
print(pref_mod__count[-1][0])


M = 10 ** 9 + 7
(n, l, r) = map(int, input().split())
p0 = r // 3 - (l - 1) // 3
p1 = (r - 1) // 3 - (l - 2) // 3
p2 = (r - 2) // 3 - (l - 3) // 3
(d0, d1, d2) = (1, 0, 0)
for _ in range(n):
	d00 = d0 * p0 + d1 * p2 + d2 * p1
	d11 = d0 * p1 + d1 * p0 + d2 * p2
	d22 = d0 * p2 + d1 * p1 + d2 * p0
	d00 %= M
	d11 %= M
	d22 %= M
	(d0, d1, d2) = (d00, d11, d22)
print(d0)


import math
from copy import deepcopy

def matrix_dot(A, B):
	size_a = (len(A), len(A[0]))
	size_b = (len(B), len(B[0]))
	assert size_a[1] == size_b[0]
	result = [[None for i in range(size_b[1])] for j in range(size_a[0])]
	for i in range(size_a[0]):
		for j in range(size_b[1]):
			result[i][j] = sum((A[i][k] * B[k][j] for k in range(size_a[1]))) % (10 ** 9 + 7)
	return result

def unit_matrix(m):
	result = [[0 for i in range(m)] for j in range(m)]
	for i in range(m):
		result[i][i] = 1
	return result

def matrix_power(A, pow):
	pows = []
	result = unit_matrix(len(A))
	while pow:
		(last_digit, pow) = (pow % 2, pow // 2)
		if not pows:
			pows.append(deepcopy(A))
		else:
			pows.append(matrix_dot(pows[-1], pows[-1]))
		if last_digit:
			result = matrix_dot(result, pows[-1])
	return result

def solve(n, l, r):
	(a, b) = ((r - l + 1) // 3, (r - l + 1) % 3)
	c = l % 3
	array = [a] * 3
	for i in range(b):
		array[(c + i) % 3] += 1
	matrix = [[array[0], array[2], array[1]], [array[1], array[0], array[2]], [array[2], array[1], array[0]]]
	array = [[ele] for ele in array]
	result = matrix_dot(matrix_power(matrix, n - 1), array)[0][0]
	return result % (10 ** 9 + 7)

def main():
	(n, l, r) = map(int, input().split())
	print(solve(n, l, r))
main()


import random
from math import floor, ceil

def solve_1(n, l, r, mod):
	c = [0] * n
	return combination(n, l, r, c, 0, [0] * 1, 0, mod)

def combination(n, l, r, c, pos, count, sum, mod):
	if pos == n:
		if sum % 3 == 0:
			count[0] = (count[0] + 1) % mod
		return
	for i in range(l, r + 1):
		c[pos] = i
		combination(n, l, r, c, pos + 1, count, sum + i, mod)
	return int(count[0])

def solve_2(n, l, r, mod):
	(c0, c1, c2) = [count(l, r, int(i)) for i in range(0, 3)]
	d = [0] * 3
	(d[0], d[1], d[2]) = (c0, c1, c2)
	for i in range(1, n):
		m0 = (d[0] * c0 + d[2] * c1 + d[1] * c2) % mod
		m1 = (d[1] * c0 + d[0] * c1 + d[2] * c2) % mod
		m2 = (d[1] * c1 + d[0] * c2 + d[2] * c0) % mod
		(d[0], d[1], d[2]) = (m0, m1, m2)
	return d[0]

def count(l, r, remainder):
	return floor((r - remainder) / 3) - ceil((l - remainder) / 3) + 1

def main():
	mod = 10 ** 9 + 7
	(n, l, r) = [int(i) for i in input().split()]
	print(solve_2(n, l, r, mod))
	return

def random_cases():
	mod = 10 ** 9 + 7
	case = [0] * 3
	case_generator(case)
	print('Case: \n' + 'n = ' + str(case[0]) + '  ' + 'l = ' + str(case[1]) + '  ' + 'r = ' + str(case[2]))
	print(solve_2(case[0], case[1], case[2], mod))
	return

def case_generator(case):
	case[0] = random.randint(1, 10)
	case[1] = random.randint(1, 10)
	case[2] = random.randint(case[1], 10)
	return

def tester():
	for i in range(1, 5):
		mod = 10 ** 9 + 7
		case = [0] * 3
		case_generator(case)
		s1 = solve_1(case[0], case[1], case[2], mod)
		s2 = solve_2(case[0], case[1], case[2], mod)
		print('Case ' + str(i) + ':\n' + 'n = ' + str(case[0]) + '  ' + 'l = ' + str(case[1]) + '  ' + 'r = ' + str(case[2]))
		print('solucion fuerza bruta : ' + str(s1))
		print('solucion eficiente : ' + str(s2))
		if s1 == s2:
			print('Accepted\n')
		else:
			print('Wrong Answer\n')
	return
main()


import os
import sys
from io import BytesIO, IOBase
import heapq as h
from bisect import bisect_left
from types import GeneratorType
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import time
start_time = time.time()
import collections as col
import math, string
from functools import reduce

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
MOD = 10 ** 9 + 7

def solve():
	(N, L, R) = getInts()
	mults = [(R - L) // 3] * 3
	mults[L % 3] += 1
	if R % 3 == (L + 1) % 3:
		mults[(L + 1) % 3] += 1
	if R % 3 == (L + 2) % 3:
		mults[(L + 1) % 3] += 1
		mults[(L + 2) % 3] += 1
	dp = [[0 for j in range(3)] for i in range(N)]
	dp[0] = mults[:]
	for i in range(1, N):
		for j in range(3):
			dp[i][j] = (dp[i - 1][j] * mults[0] + dp[i - 1][(j + 1) % 3] * mults[2] + dp[i - 1][(j + 2) % 3] * mults[1]) % MOD
	return dp[N - 1][0]
print(solve())


(n, l, r) = map(int, input().split())
d = []
mod = 1000000007
for i in range(3):
	d.append((r - i) // 3 - (l - i - 1) // 3)
(a, b, c) = (d[0], d[1], d[2])
for i in range(1, n):
	temp0 = (d[0] * a + d[1] * c + d[2] * b) % mod
	temp1 = (d[0] * b + d[1] * a + d[2] * c) % mod
	temp2 = (d[0] * c + d[1] * b + d[2] * a) % mod
	(a, b, c) = (temp0, temp1, temp2)
print(a)


import sys
mod = 10 ** 9 + 7

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def main():
	(n, l, r) = LI()
	a = [1, 0, 0]
	t = [0, 0, 0]
	k = r // 3
	t = [k] * 3
	if r % 3 > 0:
		t[1] += 1
	if r % 3 > 1:
		t[2] += 1
	k = l // 3
	t = [c - k for c in t]
	if l % 3 == 0:
		t[0] += 1
	if l % 3 > 1:
		t[1] -= 1
	for _ in range(n):
		u = [0] * 3
		for i in range(3):
			k = a[i]
			for j in range(3):
				u[(i + j) % 3] += k * t[j] % mod
		a = [c % mod for c in u]
	return a[0]
print(main())


[n, l, r] = list(map(int, input().split(' ')))
mod = 10 ** 9 + 7
qtd0 = r // 3 - (l - 1) // 3
qtd1 = (r + 1) // 3 - l // 3
qtd2 = (r + 2) // 3 - (l + 1) // 3
counts = [1, 0, 0]
for i in range(n):
	new_array = [0, 0, 0]
	new_array[0] += counts[0] * qtd0 % mod
	new_array[0] += counts[1] * qtd2 % mod
	new_array[0] += counts[2] * qtd1 % mod
	new_array[1] += counts[0] * qtd1 % mod
	new_array[1] += counts[1] * qtd0 % mod
	new_array[1] += counts[2] * qtd2 % mod
	new_array[2] += counts[0] * qtd2 % mod
	new_array[2] += counts[1] * qtd1 % mod
	new_array[2] += counts[2] * qtd0 % mod
	counts = new_array
print(counts[0] % mod)


(n, l, r) = map(int, input().split())
t = (0, 1, 2)
d = [(r - i) // 3 - (l - i - 1) // 3 for i in t]
N = 10 ** 9 + 7
a1 = d[0]
a2 = d[1]
a3 = d[2]
for w in range(1, n):
	tmp1 = (a1 * d[0] + a2 * d[2] + a3 * d[1]) % N
	tmp2 = (a1 * d[1] + a3 * d[2] + a2 * d[0]) % N
	tmp3 = (a1 * d[2] + a2 * d[1] + a3 * d[0]) % N
	(a1, a2, a3) = (tmp1, tmp2, tmp3)
print(a1)


R = lambda : map(int, input().split())
(n, l, r) = R()
(lb, rb) = ([-1] * 3, [-1] * 3)
for i in range(3):
	if l + i <= r:
		lb[(l + i) % 3] = l + i
	if r - i >= l:
		rb[(r - i) % 3] = r - i
bs = [0] * 3
for i in range(3):
	if lb[i] > 0 and rb[i] > 0:
		bs[i] = (rb[i] - lb[i]) // 3 + 1
	elif lb[i] > 0 or rb[i] > 0:
		bs[i] = 1
cnt = bs[:]
for i in range(n - 1):
	tmp = [0] * 3
	for j in range(3):
		for k in range(3):
			tmp[(j + k) % 3] += cnt[j] * bs[k]
	cnt = [x % (10 ** 9 + 7) for x in tmp]
print(cnt[0])


from math import ceil
(n, l, r) = list(map(int, input().split()))
(m0, m1, m2) = (0, 0, 0)
mod = 1000000007
m0 = r // 3 - (l - 1) // 3
m1 = (r - 1) // 3 - (l - 2) // 3
m2 = (r - 2) // 3 - (l - 3) // 3
dp = [[0 for _ in range(3)] for _ in range(n)]
dp[0][0] = m0
dp[0][1] = m1
dp[0][2] = m2
for i in range(1, n):
	dp[i][0] = (dp[i - 1][0] * m0 % mod + dp[i - 1][1] * m2 % mod + dp[i - 1][2] * m1 % mod) % mod
	dp[i][1] = (dp[i - 1][0] * m1 % mod + dp[i - 1][1] * m0 % mod + dp[i - 1][2] * m2 % mod) % mod
	dp[i][2] = (dp[i - 1][0] * m2 % mod + dp[i - 1][1] * m1 % mod + dp[i - 1][2] * m0 % mod) % mod
print(dp[n - 1][0] % mod)


(n, l, r) = map(int, input().split())
mod = 1000000007
nl = l + (3 - l % 3) % 3
nr = r - r % 3
q0 = q1 = q2 = 0
if nr >= nl:
	q0 = q1 = q2 = (nr - nl) // 3
	for i in range(r, nr, -1):
		if i % 3 == 0:
			q0 += 1
		elif i % 3 == 1:
			q1 += 1
		else:
			q2 += 1
for i in range(l, min(nl, r) + 1):
	if i % 3 == 0:
		q0 += 1
	elif i % 3 == 1:
		q1 += 1
	else:
		q2 += 1
q = [q0, q1, q2]
dp = [q] + [[0, 0, 0] for i in range(n - 1)]
for l in range(1, n):
	for m in range(3):
		ans = 0
		for i in range(3):
			ans += dp[l - 1][i] % mod * q[(m + 3 - i) % 3] % mod % mod
		dp[l][m] = ans % mod
print(dp[-1][0])


from math import ceil
(n, l, r) = map(int, input().split())
dp_0 = [0 for i in range(n)]
dp_1 = [0 for i in range(n)]
dp_2 = [0 for i in range(n)]
t = 10 ** 9 + 7
dp_0[0] = r // 3 - ceil(l / 3) + 1
dp_1[0] = (r - 1) // 3 - ceil((l - 1) / 3) + 1
dp_2[0] = (r - 2) // 3 - ceil((l - 2) / 3) + 1
for i in range(1, n):
	dp_0[i] = (dp_0[i - 1] * dp_0[0] % t + dp_1[i - 1] * dp_2[0] % t + dp_2[i - 1] * dp_1[0] % t) % t
	dp_1[i] = (dp_0[i - 1] * dp_1[0] % t + dp_1[i - 1] * dp_0[0] % t + dp_2[i - 1] * dp_2[0] % t) % t
	dp_2[i] = (dp_0[i - 1] * dp_2[0] % t + dp_1[i - 1] * dp_1[0] % t + dp_2[i - 1] * dp_0[0] % t) % t
print(dp_0[n - 1] % t)


from itertools import *
MOD = int(1000000000.0 + 7)
(n, l, r) = tuple(map(int, input().split()))
c = list(repeat(r // 3 - l // 3, 3))
for i in range(r % 3, -1, -1):
	c[i] += 1
for i in range(0, l % 3, 1):
	c[i] -= 1
dp = [[0 for _ in range(3)] for _ in range(n + 1)]
dp[1] = c
for i in range(2, n + 1):
	dpl = dp[i - 1]
	for (j, k) in product(range(3), repeat=2):
		dp[i][j] = (dp[i][j] + dpl[k] * c[(j + 3 - k) % 3]) % MOD
print(dp[n][0])


(n, mn, mx) = map(int, input('').split(' '))
MOD = 1000000007

def cntMod(l, r, m):
	lb = 0
	ub = 0
	if l % 3 == m:
		lb = l
	elif m > l % 3:
		lb = l + (m - l % 3)
	else:
		lb = l + (m + 3 - l % 3)
	if r % 3 == m:
		ub = r
	elif m < r % 3:
		ub = r - (r % 3 - m)
	else:
		ub = r - (r % 3 - m + 3)
	if lb > ub:
		return 0
	else:
		return (ub - lb) / 3 + 1
mod0 = int(cntMod(mn, mx, 0)) % MOD
mod1 = int(cntMod(mn, mx, 1)) % MOD
mod2 = int(cntMod(mn, mx, 2)) % MOD
dp = []
for i in range(n + 1):
	dp.append([None, None, None])
for i in range(n + 1):
	for j in range(3):
		if i == 0:
			if j == 0:
				dp[i][j] = 1
			else:
				dp[i][j] = 0
		else:
			a = mod0 * dp[i - 1][j] % MOD
			b = mod1 * dp[i - 1][(j + 1) % 3] % MOD
			c = mod2 * dp[i - 1][(j + 2) % 3] % MOD
			d = (a + b) % MOD
			dp[i][j] = (d + c) % MOD
print(dp[n][0] % MOD)


MOD = 10 ** 9 + 7
(n, l, r) = map(int, input().split())
dp = [[0, 0, 0] for i in range(n + 1)]
a = r // 3 - (l - 1) // 3
b = (r + 1) // 3 - (l - 1 + 1) // 3
c = (r + 2) // 3 - (l - 1 + 2) // 3
dp[1][0] = a
dp[1][1] = b
dp[1][2] = c
for i in range(1, n):
	dp[i + 1][0] = dp[i][0] * a % MOD + dp[i][1] * c % MOD + dp[i][2] * b % MOD
	dp[i + 1][1] = dp[i][0] * b % MOD + dp[i][1] * a % MOD + dp[i][2] * c % MOD
	dp[i + 1][2] = dp[i][0] * c % MOD + dp[i][1] * b % MOD + dp[i][2] * a % MOD
print(dp[n][0] % MOD)


(n, l, r) = map(int, input().split())
mod = 10 ** 9 + 7
new_l = 0
new_r = 0
if l % 3 == 0:
	new_l = l
elif l % 3 == 1:
	new_l = l - 1
else:
	new_l = l - 2
if r % 3 == 2:
	new_r = r
elif r % 3 == 1:
	new_r = r + 1
else:
	new_r = r + 2

def count(mod):
	f_l = lambda x: sum((1 if i % 3 == x else 0 for i in range(new_l, l)))
	f_r = lambda x: sum((1 if i % 3 == x else 0 for i in range(r + 1, new_r + 1)))
	return (new_r - new_l + 1) // 3 - f_r(mod) - f_l(mod)
init = {0: count(0), 1: count(1), 2: count(2)}
a = {0: init[0], 1: init[1], 2: init[2]}
for i in range(1, n):
	a0 = (a[0] * init[0] + a[2] * init[1] + a[1] * init[2]) % mod
	a1 = (a[1] * init[0] + a[0] * init[1] + a[2] * init[2]) % mod
	a2 = (a[2] * init[0] + a[1] * init[1] + a[0] * init[2]) % mod
	a[0] = a0
	a[1] = a1
	a[2] = a2
print(a[0])


import math
mod = 10 ** 9 + 7
(n, L, R) = map(int, input().strip().split())
ini = math.ceil(L / 3)
end = math.floor(R / 3)
n0 = end - ini + 1
n1 = math.floor((R - 1) / 3) - math.ceil((L - 1) / 3) + 1
n2 = math.floor((R - 2) / 3) - math.ceil((L - 2) / 3) + 1
dp = [[0 for i in range(n)] for i in range(3)]
dp[0][0] = n0
dp[1][0] = n1
dp[2][0] = n2
for i in range(1, n):
	dp[0][i] = (dp[1][i - 1] * n2 + dp[2][i - 1] * n1 + dp[0][i - 1] * n0) % mod
	dp[1][i] = (dp[0][i - 1] * n1 + dp[2][i - 1] * n2 + dp[1][i - 1] * n0) % mod
	dp[2][i] = (dp[0][i - 1] * n2 + dp[1][i - 1] * n1 + dp[2][i - 1] * n0) % mod
print(dp[0][-1])


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from functools import cmp_to_key
from heapq import *
from math import gcd, factorial, floor, ceil, sqrt
from copy import deepcopy
from collections import deque
from bisect import bisect_left as bl
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def zerolist(n):
	return [0] * n

def nextline():
	out('\n')

def testcase(t):
	for pp in range(t):
		solve(pp)

def printlist(a):
	for p in range(0, len(a)):
		out(str(a[p]) + ' ')

def google(p):
	print('Case #' + str(p) + ': ', end='')

def lcm(a, b):
	return a * b // gcd(a, b)

def power(x, y, p):
	y %= p - 1
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def ncr(n, r):
	return factorial(n) // (factorial(r) * factorial(max(n - r, 1)))

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True
inf = pow(10, 20)
mod = 10 ** 9 + 7
dp = [[-1, -1, -1] for i in range(300010)]

@iterative
def rec(pos, rem):
	global a, b, c, n, mod
	if pos >= n:
		if rem == 0:
			yield 1
		else:
			yield (-inf)
	if dp[pos][rem] != -1:
		yield dp[pos][rem]
	temp = 0
	temp += max(0, a * (yield rec(pos + 1, (rem + 1) % 3))) % mod
	temp += max(0, b * (yield rec(pos + 1, (rem + 2) % 3))) % mod
	temp += max(0, c * (yield rec(pos + 1, rem % 3))) % mod
	temp %= mod
	dp[pos][rem] = temp
	yield temp

def solve(case):
	global a, b, c, n
	(n, l, r) = sep()
	c = r // 3 - (l - 1) // 3
	a = (r + 2) // 3 - (l + 1) // 3
	b = (r + 1) // 3 - l // 3
	print(rec(0, 0) % mod)
(a, b, c, n) = (0, 0, 0, 0)
testcase(1)


(n, l, r) = map(int, input().split())
ost0 = r // 3 - (l - 1) // 3
ost1 = ost0
if l % 3 == 0:
	ost2 = ost0 - 1
if l % 3 == 1:
	ost2 = ost0
if l % 3 == 2:
	ost2 = ost0
if r % 3 == 2:
	ost2 += 1
if l % 3 == 0:
	ost1 = ost2
if l % 3 == 1:
	ost1 = ost2
if l % 3 == 2:
	ost1 = ost2 - 1
if r % 3 == 1:
	ost1 += 1
dp = []
for i in range(n):
	dp.append([0, 0, 0])
(dp[0][0], dp[0][1], dp[0][2]) = (ost0, ost1, ost2)
mmm = [ost0, ost1, ost2]
for i in range(1, n):
	for j in range(3):
		dp[i][j] = (dp[i - 1][0] * mmm[j] + dp[i - 1][1] * mmm[(j - 1) % 3] + dp[i - 1][2] * mmm[(j - 2) % 3]) % (10 ** 9 + 7)
print(dp[-1][0] % (10 ** 9 + 7))


(n, l, r) = map(int, input().split())
pri = 10 ** 9 + 7
if l % 3 == 0:
	k1 = r // 3 - l // 3 + 1
else:
	k1 = r // 3 - l // 3
j = l - 1
q = r - 1
if j % 3 == 0:
	k2 = q // 3 - j // 3 + 1
else:
	k2 = q // 3 - j // 3
j = l - 2
q = r - 2
if j % 3 == 0:
	k3 = q // 3 - j // 3 + 1
else:
	k3 = q // 3 - j // 3
dp = [[0 for i in range(n + 1)] for i in range(3)]
dp[0][1] = k1
dp[1][1] = k2
dp[2][1] = k3
for i in range(2, len(dp[0])):
	dp[0][i] = dp[0][i - 1] * k1 + dp[1][i - 1] * k3 + dp[2][i - 1] * k2
	dp[1][i] = dp[1][i - 1] * k1 + dp[2][i - 1] * k3 + dp[0][i - 1] * k2
	dp[2][i] = dp[2][i - 1] * k1 + dp[0][i - 1] * k3 + dp[1][i - 1] * k2
	dp[0][i] %= pri
	dp[1][i] %= pri
	dp[2][i] %= pri
print(dp[0][-1])


MOD = 1000000007
MOD2 = 998244353
ii = lambda : int(input())
si = lambda : input()
dgl = lambda : list(map(int, input()))
f = lambda : map(int, input().split())
il = lambda : list(map(int, input().split()))
ls = lambda : list(input())
let = '@abcdefghijklmnopqrstuvwxyz'
(n, l, r) = f()
arr = [[0 for i in range(3)] for j in range(n)]
th = [r // 3 - (l - 1) // 3, (r - 1) // 3 - (l - 2) // 3, (r - 2) // 3 - (l - 3) // 3]
arr[0][0] = th[0]
arr[0][1] = th[1]
arr[0][2] = th[2]
for i in range(1, n):
	arr[i][0] = (arr[i - 1][0] * th[0] % MOD + arr[i - 1][1] * th[2] % MOD + arr[i - 1][2] * th[1] % MOD) % MOD
	arr[i][1] = (arr[i - 1][1] * th[0] % MOD + arr[i - 1][0] * th[1] % MOD + arr[i - 1][2] * th[2] % MOD) % MOD
	arr[i][2] = (arr[i - 1][2] * th[0] % MOD + arr[i - 1][0] * th[2] % MOD + arr[i - 1][1] * th[1] % MOD) % MOD
print(arr[n - 1][0])


MOD = 10 ** 9 + 7
(n, l, r) = list(map(int, input().split()))
lr_counts = [(r - l + 1) // 3] * 3
for i in range(l + sum(lr_counts), r + 1):
	lr_counts[i % 3] += 1
cur_counts = [1, 0, 0]
for _ in range(n):
	new_counts = [0, 0, 0]
	for j in range(3):
		for k in range(3):
			new_counts[(j + k) % 3] += cur_counts[j] * lr_counts[k]
	for j in range(3):
		cur_counts[j] = new_counts[j] % MOD
print(cur_counts[0])


[n, l, r] = [int(i) for i in input().split(' ')]
answer = 0
mod = []
if l == r:
	if n * l % 3 == 0:
		answer = 1
else:
	surplus = (r - l + 1) % 3
	mod = [int((r - l + 1 - surplus) / 3)] * 3
	if surplus == 1:
		mod[r % 3] += 1
	if surplus == 2:
		mod[r % 3] += 1
		mod[(r - 1) % 3] += 1
	dp = [[0] * (n + 1) for i in range(3)]
	dp[0][0] = 1
	for i in range(1, n + 1):
		for j in range(3):
			dp[j][i] = (dp[j][i - 1] * mod[0] + dp[(j + 1) % 3][i - 1] * mod[2] + dp[(j + 2) % 3][i - 1] * mod[1]) % 1000000007
	answer = dp[0][n]
print(answer)


(n, l, r) = map(int, input().split())
s = [0] * 3
MOD = 10 ** 9 + 7
if r - l <= 3:
	for i in range(l, r + 1):
		s[i % 3] += 1
else:
	while l % 3 != 0:
		s[l % 3] += 1
		l += 1
	while r % 3 != 0:
		s[r % 3] += 1
		r -= 1
	for i in range(3):
		s[i] += (r - l) // 3 + int(i % 3 == 0)
dp = [[0] * 3 for i in range(n + 1)]
dp[0][0] = 1
for i in range(n):
	dp[i + 1][0] += dp[i][0] * s[0] + dp[i][1] * s[2] + dp[i][2] * s[1]
	dp[i + 1][0] %= MOD
	dp[i + 1][1] += dp[i][0] * s[1] + dp[i][1] * s[0] + dp[i][2] * s[2]
	dp[i + 1][1] %= MOD
	dp[i + 1][2] += dp[i][0] * s[2] + dp[i][1] * s[1] + dp[i][2] * s[0]
	dp[i + 1][2] %= MOD
print(dp[n][0])


import sys
from math import floor, ceil
r = lambda : sys.stdin.readline().strip()
MOD = int(1000000000.0 + 7)
(n, l, r) = map(int, r().split())
modThree = [0] * 3
modThree[0] = floor(r / 3) - ceil(l / 3) + 1
modThree[1] = floor((r - 1) / 3) - ceil((l - 1) / 3) + 1
modThree[2] = floor((r - 2) / 3) - ceil((l - 2) / 3) + 1
d = [[0] * 3 for i in range(n + 1)]
d[1][0] = modThree[0]
d[1][1] = modThree[1]
d[1][2] = modThree[2]
for i in range(2, n + 1):
	d[i][0] = (d[i - 1][0] * modThree[0] + d[i - 1][1] * modThree[2] + d[i - 1][2] * modThree[1]) % MOD
	d[i][1] = (d[i - 1][0] * modThree[1] + d[i - 1][1] * modThree[0] + d[i - 1][2] * modThree[2]) % MOD
	d[i][2] = (d[i - 1][0] * modThree[2] + d[i - 1][1] * modThree[1] + d[i - 1][2] * modThree[0]) % MOD
print(d[n][0])


inf = pow(10, 9) + 7
(n, l, r) = map(int, input().split())
list1 = [[], [], []]
for i in range(n):
	list1[0].append(0)
	list1[1].append(0)
	list1[2].append(0)
list2 = list()
s = l % 3
(x, y, z) = (0, 0, 0)
if s == 0:
	x = (r - l) // 3 + 1
	y = (r - l - 1) // 3 + 1
	z = (r - l - 2) // 3 + 1
elif s == 1:
	y = (r - l) // 3 + 1
	z = (r - 1 - l) // 3 + 1
	x = (r - l - 2) // 3 + 1
else:
	z = (r - l) // 3 + 1
	x = (r - l - 1) // 3 + 1
	y = (r - l - 2) // 3 + 1
list1[0][0] = x % inf
list1[1][0] = y % inf
list1[2][0] = z % inf
for i in range(1, n):
	zeroth = list1[0][0] * list1[0][i - 1] % inf + list1[1][i - 1] * list1[2][0] % inf + list1[2][i - 1] * list1[1][0] % inf
	one = list1[0][0] * list1[1][i - 1] % inf + list1[1][0] * list1[0][i - 1] % inf + list1[2][i - 1] * list1[2][0] % inf
	two = list1[0][i - 1] * list1[2][0] % inf + list1[2][i - 1] * list1[0][0] % inf + list1[1][i - 1] * list1[1][0] % inf
	list1[0][i] += zeroth % inf
	list1[1][i] += one % inf
	list1[2][i] += two % inf
print(list1[0][n - 1] % inf)


(n, l, r) = map(int, input().strip().split(' '))
a = [0, 0, 0]
a[0] = a[1] = a[2] = (r - l + 1) // 3
if (r - l + 1) % 3 == 2:
	a[1] += 1
	a[2] += 1
elif (r - l + 1) % 3 == 1:
	a[1] += 1
if l % 3 == 2:
	a = [a[2], a[0], a[1]]
elif l % 3 == 0:
	a = [a[1], a[2], a[0]]
m = 1000000007
now0 = [0] * (n + 1)
now1 = [0] * (n + 1)
now2 = [0] * (n + 1)
now2[1] = a[2]
now0[1] = a[0]
now1[1] = a[1]
for i in range(2, n + 1):
	now0[i] = (now0[i - 1] * a[0] + now1[i - 1] * a[2] + now2[i - 1] * a[1]) % m
	now1[i] = (now0[i - 1] * a[1] + now1[i - 1] * a[0] + now2[i - 1] * a[2]) % m
	now2[i] = (now0[i - 1] * a[2] + now1[i - 1] * a[1] + now2[i - 1] * a[0]) % m
print(now0[n] % m)


from math import floor
n_l_r = [int(i) for i in input().split()]
arr = []
module = 10 ** 9 + 7
for i in range(3):
	arr.append(floor((n_l_r[2] - i) / 3) - floor((n_l_r[1] - i - 1) / 3))
a = arr[0]
b = arr[1]
c = arr[2]
for _ in range(1, n_l_r[0]):
	aux_arr1 = (a * arr[0] + b * arr[2] + c * arr[1]) % module
	aux_arr2 = (a * arr[1] + b * arr[0] + c * arr[2]) % module
	aux_arr3 = (a * arr[2] + b * arr[1] + c * arr[0]) % module
	a = aux_arr1
	b = aux_arr2
	c = aux_arr3
print(a)


(n, l, r) = map(int, input().split())
mod = 1000000007
valor1 = 0
valor2 = 0
valor3 = 0
cont1 = l
cont2 = r
if r % 3 == 1:
	valor1 += 1
	cont2 = r - 1
if r % 3 == 2:
	valor1 += 1
	valor2 += 1
	cont2 = r - 2
if l % 3 == 1:
	valor1 += 1
	valor2 += 1
	cont1 = l + 2
if l % 3 == 2:
	valor2 += 1
	cont1 = l + 1
item = (cont2 - cont1) // 3
valor1 = valor1 + item
valor2 = valor2 + item
valor3 = valor3 + item + 1
cont1 = valor1
cont2 = valor2
saida = valor3
for num in range(1, n):
	i = (cont1 * valor3 + cont2 * valor2 + saida * valor1) % mod
	j = (cont1 * valor1 + cont2 * valor3 + saida * valor2) % mod
	k = (cont1 * valor2 + cont2 * valor1 + saida * valor3) % mod
	cont1 = i
	cont2 = j
	saida = k
print(saida)


from math import *
(n, l, r) = map(int, input().split())
a = floor(r / 3) - ceil(l / 3) + 1
b = floor((r - 1) / 3) - ceil((l - 1) / 3) + 1
c = floor((r - 2) / 3) - ceil((l - 2) / 3) + 1
m = 1000000007
dp = [[0] * (n + 1) for i in range(3)]
dp[0][1] = a
dp[1][1] = b
dp[2][1] = c
for l in range(2, n + 1):
	dp[0][l] = (dp[0][l - 1] * a + dp[1][l - 1] * c + dp[2][l - 1] * b) % m
	dp[1][l] = (dp[0][l - 1] * b + dp[1][l - 1] * a + dp[2][l - 1] * c) % m
	dp[2][l] = (dp[0][l - 1] * c + dp[1][l - 1] * b + dp[2][l - 1] * a) % m
print(dp[0][n] % m)


from sys import stdin
input = lambda : stdin.readline().strip()
from math import ceil, sqrt, factorial, gcd
from collections import deque
(n, l, r) = map(int, input().split())
d = []
for i in range(3):
	d.append((r - i) // 3 - (l - i - 1) // 3)
mod = 10 ** 9 + 7
(a, b, c) = (d[0], d[1], d[2])
for _ in range(1, n):
	temp1 = (a * d[0] + b * d[2] + c * d[1]) % mod
	temp2 = (a * d[1] + b * d[0] + c * d[2]) % mod
	temp3 = (a * d[2] + b * d[1] + c * d[0]) % mod
	(a, b, c) = (temp1, temp2, temp3)
print(a)


def main():
	arr = input().split()
	n = int(arr[0])
	l = int(arr[1])
	r = int(arr[2])
	mod = 10 ** 9 + 7
	arr = [1, 0, 0]
	mod0 = r // 3 - (l - 1) // 3
	mod1 = (r + 2) // 3 - (l - 1 + 2) // 3
	mod2 = (r + 1) // 3 - (l - 1 + 1) // 3
	for _ in range(n):
		dup = [0, 0, 0]
		dup[0] = (arr[0] * mod0 + arr[1] * mod2 + arr[2] * mod1) % mod
		dup[1] = (arr[0] * mod1 + arr[1] * mod0 + arr[2] * mod2) % mod
		dup[2] = (arr[0] * mod2 + arr[1] * mod1 + arr[2] * mod0) % mod
		arr = dup.copy()
	print(arr[0])
main()


import math
(n, l, r) = map(int, input().split(' '))
zero = math.floor(r / 3) - math.ceil(l / 3) + 1
one = math.floor((r - 1) / 3) - math.ceil((l - 1) / 3) + 1
two = math.floor((r - 2) / 3) - math.ceil((l - 2) / 3) + 1
a = [zero, one, two]
mod = 10 ** 9 + 7
dp = [[1 for i in range(n)] for i in range(3)]
for i in range(n):
	for j in range(3):
		if i == 0:
			dp[j][i] = a[j]
		elif j == 0:
			dp[j][i] = (dp[j][i - 1] * a[0] + dp[j + 1][i - 1] * a[2] + dp[j + 2][i - 1] * a[1]) % mod
		elif j == 1:
			dp[j][i] = (dp[j - 1][i - 1] * a[1] + dp[j][i - 1] * a[0] + dp[j + 1][i - 1] * a[2]) % mod
		else:
			dp[j][i] = (dp[j - 2][i - 1] * a[2] + dp[j - 1][i - 1] * a[1] + dp[j][i - 1] * a[0]) % mod
print(dp[0][n - 1])


(n, l, r) = [int(i) for i in input().split()]
number_of_zeros = 0
number_of_ones = 0
number_of_twos = 0
if l % 3 == 0:
	if r % 3 == 0:
		number_of_zeros = (r - l + 1) // 3 + 1
		number_of_ones = (r - l + 1) // 3
		number_of_twos = (r - l + 1) // 3
	if r % 3 == 1:
		number_of_zeros = (r - l + 1) // 3 + 1
		number_of_ones = (r - l + 1) // 3 + 1
		number_of_twos = (r - l + 1) // 3
	if r % 3 == 2:
		number_of_zeros = (r - l + 1) // 3
		number_of_ones = (r - l + 1) // 3
		number_of_twos = (r - l + 1) // 3
elif l % 3 == 1:
	if r % 3 == 0:
		number_of_zeros = (r - l + 1) // 3
		number_of_ones = (r - l + 1) // 3
		number_of_twos = (r - l + 1) // 3
	if r % 3 == 1:
		number_of_zeros = (r - l + 1) // 3
		number_of_ones = (r - l + 1) // 3 + 1
		number_of_twos = (r - l + 1) // 3
	if r % 3 == 2:
		number_of_zeros = (r - l + 1) // 3
		number_of_ones = (r - l + 1) // 3 + 1
		number_of_twos = (r - l + 1) // 3 + 1
elif l % 3 == 2:
	if r % 3 == 0:
		number_of_zeros = (r - l + 1) // 3 + 1
		number_of_ones = (r - l + 1) // 3
		number_of_twos = (r - l + 1) // 3 + 1
	if r % 3 == 1:
		number_of_zeros = (r - l + 1) // 3
		number_of_ones = (r - l + 1) // 3
		number_of_twos = (r - l + 1) // 3
	elif r % 3 == 2:
		number_of_zeros = (r - l + 1) // 3
		number_of_ones = (r - l + 1) // 3
		number_of_twos = (r - l + 1) // 3 + 1
dp = [[-1 for i in range(3)] for j in range(n + 1)]
MOD = 10 ** 9 + 7
dp[1][0] = number_of_zeros % MOD
dp[1][1] = number_of_ones % MOD
dp[1][2] = number_of_twos % MOD
for i in range(2, n + 1):
	dp[i][0] = (dp[i - 1][0] % MOD * (number_of_zeros % MOD) % MOD + dp[i - 1][1] % MOD * (number_of_twos % MOD) % MOD + dp[i - 1][2] % MOD * (number_of_ones % MOD) % MOD) % MOD
	dp[i][1] = (dp[i - 1][0] % MOD * (number_of_ones % MOD) % MOD + dp[i - 1][1] % MOD * (number_of_zeros % MOD) % MOD + dp[i - 1][2] % MOD * (number_of_twos % MOD) % MOD) % MOD
	dp[i][2] = (dp[i - 1][0] % MOD * (number_of_twos % MOD) % MOD + dp[i - 1][1] % MOD * (number_of_ones % MOD) % MOD + dp[i - 1][2] % MOD * number_of_zeros % MOD % MOD) % MOD
if dp[n][0] != -1:
	print(dp[n][0] % MOD)
else:
	print(0)


(n, l, r) = map(int, input().split())
total = r - l + 1
(rf, re) = (l % 3, r % 3)
if rf == 0:
	rf = 3
(l, r) = (l + (3 - rf), r - re)
if rf == 3:
	rf = 0
mod = int(1000000000.0 + 7)
zeros = ((r - l) // 3 + 1) % mod
ones = ((rf == 1) * 1 + (r - l) // 3 + (re >= 1) * 1) % mod
twos = ((rf >= 1) * 1 + (r - l) // 3 + (re == 2) * 1) % mod
dp = [[None] * 3 for _ in range(n + 1)]
(dp[1][0], dp[1][1], dp[1][2]) = (zeros, ones, twos)
for i in range(2, n + 1):
	dp[i][0] = (dp[i - 1][0] % mod * zeros % mod + dp[i - 1][1] % mod * twos % mod + dp[i - 1][2] % mod * ones % mod) % mod
	dp[i][1] = (dp[i - 1][0] % mod * ones % mod + dp[i - 1][1] % mod * zeros % mod + dp[i - 1][2] % mod * twos % mod) % mod
	dp[i][2] = (dp[i - 1][0] % mod * twos % mod + dp[i - 1][1] % mod * ones % mod + dp[i - 1][2] % mod * zeros % mod) % mod
print(dp[n][0])


import sys
from bisect import bisect_left, bisect_right, insort
from collections import deque, Counter
from math import gcd, sqrt, factorial, ceil, log10, log2, floor
from itertools import permutations
from heapq import heappush, heappop, heapify
inf = float('inf')
mod = 10 ** 9 + 7

def factorial_p(n, p):
	ans = 1
	if n <= p // 2:
		for i in range(1, n + 1):
			ans = ans * i % p
	else:
		for i in range(1, p - n):
			ans = ans * i % p
		ans = pow(ans, p - 2, p)
		if n % 2 == 0:
			ans = p - ans
	return ans

def nCr_p(n, r, p):
	ans = 1
	while n != 0 or r != 0:
		(a, b) = (n % p, r % p)
		if a < b:
			return 0
		ans = ans * factorial_p(a, p) * pow(factorial_p(b, p), p - 2, p) * pow(factorial_p(a - b, p), p - 2, p) % p
		n //= p
		r //= p
	return ans

def prime_sieve(n):
	flag = n % 6 == 2
	sieve = bytearray((n // 3 + flag >> 3) + 1)
	for i in range(1, int(n ** 0.5) // 3 + 1):
		if not sieve[i >> 3] >> (i & 7) & 1:
			k = 3 * i + 1 | 1
			for j in range(k * k // 3, n // 3 + flag, 2 * k):
				sieve[j >> 3] |= 1 << (j & 7)
			for j in range(k * (k - 2 * (i & 1) + 4) // 3, n // 3 + flag, 2 * k):
				sieve[j >> 3] |= 1 << (j & 7)
	return sieve

def prime_list(n):
	res = []
	if n > 1:
		res.append(2)
	if n > 2:
		res.append(3)
	if n > 4:
		sieve = prime_sieve(n + 1)
		res.extend((3 * i + 1 | 1 for i in range(1, (n + 1) // 3 + (n % 6 == 1)) if not sieve[i >> 3] >> (i & 7) & 1))
	return res

def is_prime(n):
	if n < 5 or n & 1 == 0 or n % 3 == 0:
		return 2 <= n <= 3
	s = (n - 1 & 1 - n).bit_length() - 1
	d = n >> s
	for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
		p = pow(a, d, n)
		if p == 1 or p == n - 1 or a % n == 0:
			continue
		for _ in range(s):
			p = p * p % n
			if p == n - 1:
				break
		else:
			return False
	return True

def all_factors(n):
	(small, large) = ([], [])
	for i in range(1, int(n ** 0.5) + 1, 2 if n & 1 else 1):
		if not n % i:
			small.append(i)
			large.append(n // i)
	large.reverse()
	small.extend(large)
	return small

def count(n):
	return n * (n + 1) // 2

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()
(n, l, r) = get_ints()
sub = r - l + 1
num = [sub // 3] * 3
if sub % 3 == 1:
	num[l % 3] += 1
elif sub % 3 == 2:
	num[l % 3] += 1
	num[(l + 1) % 3] += 1
dp = [1, 0, 0]
for i in range(n):
	temp = [0, 0, 0]
	temp[0] = dp[0] * num[0] + dp[1] * num[2] + dp[2] * num[1]
	temp[1] = dp[2] * num[2] + dp[0] * num[1] + dp[1] * num[0]
	temp[2] = dp[1] * num[1] + dp[0] * num[2] + dp[2] * num[0]
	for j in range(3):
		dp[j] = temp[j] % mod
print(dp[0])


import sys
MOD = int(1000000000.0 + 7)
import time

def solve(n, l, r):
	dp = [[0] * 3 for _ in range(n)]
	add_num = [r // 3 - (l - 1) // 3, (r + 2) // 3 - (l + 2 - 1) // 3, (r + 1) // 3 - (l + 1 - 1) // 3]
	add_num = [i % MOD for i in add_num]
	for k in range(3):
		dp[0][k] += add_num[k]
	for i in range(1, n):
		for j in range(3):
			for k in range(3):
				dp[i][j] += dp[i - 1][(j - k + 3) % 3] * add_num[k] % MOD
				dp[i][j] %= MOD
	print(dp[n - 1][0])
while True:
	try:
		(n, l, r) = [int(x) for x in input().split()]
		solve(n, l, r)
	except EOFError:
		break


(n, l, r) = map(int, input().split())
count = [0, 0, 0]
mod = 10 ** 9 + 7
for i in range(3):
	if l + i <= r:
		count[(l + i) % 3] += 1 + (r - (l + i)) // 3
run = count[:]
for i in range(n - 1):
	zero = (run[0] * count[0] % mod + run[1] * count[2] % mod + run[2] * count[1] % mod) % mod
	one = (run[0] * count[1] % mod + run[1] * count[0] % mod + run[2] * count[2] % mod) % mod
	two = (run[0] * count[2] % mod + run[1] * count[1] % mod + run[2] * count[0] % mod) % mod
	run = [zero, one, two]
print(run[0])


import sys
import math
import collections
import operator as op
from collections import deque
from math import gcd, inf, sqrt, pi, cos, sin
from bisect import bisect_right, bisect_left
from functools import reduce
from sys import stdin, stdout, setrecursionlimit
setrecursionlimit(2 ** 20)

def factorial(n):
	if n == 0:
		return 1
	return n * factorial(n - 1)

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer // denom

def prime_factors(n):
	i = 2
	factors = []
	while i * i <= n:
		if n % i:
			i += 1
		else:
			n //= i
			factors.append(i)
	if n > 1:
		factors.append(n)
	return len(set(factors))

def isPowerOfTwo(x):
	return x and (not x & x - 1)

def factors(n):
	return list(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))

def mod0cnt(n):
	return n // 3

def mod1cnt(n):
	return n // 3 + (n % 3 != 0)

def mod2cnt(n):
	return n // 3 + (n % 3 == 2) + 1
MOD = 1000000007
T = 1
for _ in range(T):
	(n, l, r) = list(map(int, stdin.readline().split()))
	mod0 = mod0cnt(r) - mod0cnt(l - 1)
	mod1 = mod1cnt(r) - mod1cnt(l - 1)
	mod2 = mod2cnt(r) - mod2cnt(l - 1)
	dp = [[0 for j in range(3)] for i in range(n)]
	dp[0][0] = mod0
	dp[0][1] = mod1
	dp[0][2] = mod2
	for i in range(n):
		if i == 0:
			continue
		dp[i][0] = dp[i - 1][0] * mod0 + dp[i - 1][1] * mod2 + dp[i - 1][2] * mod1
		dp[i][1] = dp[i - 1][0] * mod1 + dp[i - 1][1] * mod0 + dp[i - 1][2] * mod2
		dp[i][2] = dp[i - 1][0] * mod2 + dp[i - 1][1] * mod1 + dp[i - 1][2] * mod0
		dp[i][0] %= MOD
		dp[i][1] %= MOD
		dp[i][2] %= MOD
	print(dp[n - 1][0])


from math import ceil
mod = 10 ** 9 + 7

def f(l, r, x):
	return ceil((r - x) / 3) - ceil((l - 1 - x) / 3)
(n, l, r) = map(int, input().split())
m1 = f(l, r, 0)
m2 = f(l, r, 1)
m0 = f(l, r, 2)
dp0 = [1 for i in range(n + 1)]
dp1 = [0 for i in range(n + 1)]
dp2 = [0 for i in range(n + 1)]
for i in range(1, n + 1):
	dp0[i] = (dp0[i - 1] * m0 + dp1[i - 1] * m2 + dp2[i - 1] * m1) % mod
	dp1[i] = (dp1[i - 1] * m0 + dp2[i - 1] * m2 + dp0[i - 1] * m1) % mod
	dp2[i] = (dp2[i - 1] * m0 + dp0[i - 1] * m2 + dp1[i - 1] * m1) % mod
print(dp0[n])


def mod(x):
	return x % 1000000007
(n, l, r) = map(int, input().split())
res = 0
if l == r:
	if l * n % 3 == 0:
		res = 1
	print(res)
	exit()
if n == 1:
	while l % 3 > 0:
		l = l + 1
	if r - l >= 0:
		res = 1 + (r - l) // 3
	print(res)
	exit()
x = [0, 0, 0]
x[l % 3] = max(0, 1 + (r - l) // 3)
x[(l + 1) % 3] = max(0, 1 + (r - l - 1) // 3)
x[(l + 2) % 3] = max(0, 1 + (r - l - 2) // 3)
res = [x[0], x[1], x[2]]
for i in range(1, n):
	a0 = res[0] * x[0] + res[1] * x[2] + res[2] * x[1]
	a1 = res[0] * x[1] + res[1] * x[0] + res[2] * x[2]
	a2 = res[0] * x[2] + res[1] * x[1] + res[2] * x[0]
	res = [mod(a0), mod(a1), mod(a2)]
print(res[0])


from sys import stdin, stdout
from collections import defaultdict
import math
I = stdin.readline
P = stdout.write
(n, l, r) = map(int, I().split())
(a, b, c) = (0, 0, 0)
if l % 3 == 0:
	a = (r - l) // 3 + 1
	b = (r - l - 1) // 3 + 1
	c = r - l + 1 - a - b
elif l % 3 == 1:
	b = (r - l) // 3 + 1
	a = (r - l - 2) // 3 + 1
	c = r - l + 1 - a - b
else:
	c = (r - l) // 3 + 1
	a = (r - l - 1) // 3 + 1
	b = r - l + 1 - a - c
mod = 10 ** 9 + 7
dp = [[0 for i in range(3)] for i in range(n + 1)]
mul = [a, b, c]
dp[1][0] = a
dp[1][1] = b
dp[1][2] = c
for i in range(2, n + 1):
	dp[i][0] = (dp[i - 1][0] * a + dp[i - 1][1] * c + dp[i - 1][2] * b) % mod
	dp[i][1] = (dp[i - 1][0] * b + dp[i - 1][1] * a + dp[i - 1][2] * c) % mod
	dp[i][2] = (dp[i - 1][0] * c + dp[i - 1][1] * b + dp[i - 1][2] * a) % mod
print(dp[n][0])


(n, l, r) = map(int, input().split())
dp = [[0, 0, 0] for i in range(n)]
MOD = int(1000000000.0 + 7)
t0 = r // 3 - (l - 1) // 3
t1 = (r - 1) // 3 - (l + 1) // 3 + 1
t2 = r - l - t0 - t1 + 1
dp[0][0] = t0 % MOD
dp[0][1] = t1 % MOD
dp[0][2] = t2 % MOD
i = 1
while i < n:
	dp[i][0] = (dp[i - 1][0] * t0 + dp[i - 1][1] * t2 + dp[i - 1][2] * t1) % MOD
	dp[i][1] = (dp[i - 1][0] * t1 + dp[i - 1][1] * t0 + dp[i - 1][2] * t2) % MOD
	dp[i][2] = (dp[i - 1][0] * t2 + dp[i - 1][1] * t1 + dp[i - 1][2] * t0) % MOD
	i += 1
print(dp[n - 1][0] % MOD)


import sys
import math
import operator as op
from functools import reduce
from bisect import *

def read_line():
	return sys.stdin.readline()[:-1]

def read_int():
	return int(sys.stdin.readline())

def read_int_line():
	return [int(v) for v in sys.stdin.readline().split()]

def read_float_line():
	return [float(v) for v in sys.stdin.readline().split()]

def ncr(n, r):
	r = min(r, n - r)
	numer = reduce(op.mul, range(n, n - r, -1), 1)
	denom = reduce(op.mul, range(1, r + 1), 1)
	return numer / denom
N = int(1000000.0) + 10
fenwick = [0] * N

def add(i, x, n):
	while i < n:
		fenwick[i] += x
		i = i | i + 1

def fsum(i, n):
	res = 0
	while i >= 0:
		res += fenwick[i]
		i = (i & i + 1) - 1
	return res

def fsum_range(i, j, n):
	return fsum(j, n) - fsum(i - 1, n)
mod = int(1000000000.0) + 7
t = 1
for i in range(t):
	(n, l, r) = read_int_line()
	dp = [[0, 0, 0] for i in range(n)]
	if r % 3 != 0 and l % 3 != 0:
		a1 = r // 3 - l // 3
	elif r % 3 != 0 and l % 3 == 0:
		a1 = r // 3 - l // 3
	elif r % 3 == 0 and l % 3 != 0:
		a1 = r // 3 - l // 3 - 1
	else:
		a1 = r // 3 - l // 3 - 1
	if l % 3 == 0 and l != r:
		a1 += 1
	if r % 3 == 0:
		a1 += 1
	a2 = a1
	if l % 3 == 1:
		a2 += 1
	if r % 3 == 0:
		a2 -= 1
	a3 = r - l + 1 - a1 - a2
	dp[0][0] = a1 % mod
	dp[0][1] = a2 % mod
	dp[0][2] = a3 % mod
	for i in range(1, n):
		dp[i][0] = (a1 * dp[i - 1][0] + dp[i - 1][1] * a3 + dp[i - 1][2] * a2) % mod
		dp[i][1] = (a2 * dp[i - 1][0] + dp[i - 1][1] * a1 + dp[i - 1][2] * a3) % mod
		dp[i][2] = (a3 * dp[i - 1][0] + dp[i - 1][1] * a2 + dp[i - 1][2] * a1) % mod
	print(dp[n - 1][0])


(n, l, r) = map(int, input().split())
length = l - r + 1
mod = int(1000000000.0 + 7)
zero = r // 3 - (l - 1) // 3
one = (r + 2) // 3 - (l + 1) // 3
two = (r + 1) // 3 - l // 3

def num(n, s):
	rec = [[0 for j in range(3)] for i in range(n + 1)]
	rec[1][0] = zero
	rec[1][1] = two
	rec[1][2] = one
	for i in range(2, n + 1):
		for j in range(3):
			rec[i][j] = (zero * rec[i - 1][j % 3] + one * rec[i - 1][(j + 1) % 3] + two * rec[i - 1][(j + 2) % 3]) % mod
	return rec[n][0]
result = num(n, 0)
print(result % mod)


(n, l, r) = map(int, input().split())
k = (r - l + 1) // 3
(f, N) = ([[k], [k], [k]], 10 ** 9 + 7)
for _ in range((r - l + 1) % 3):
	f[(r - _) % 3][0] += 1
(a, b, c) = (f[0][0], f[1][0], f[2][0])
for i in range(n - 1):
	x = (a * f[0][0] + b * f[2][0] + c * f[1][0]) % N
	y = (a * f[1][0] + b * f[0][0] + c * f[2][0]) % N
	z = (b * f[1][0] + c * f[0][0] + a * f[2][0]) % N
	(a, b, c) = (x, y, z)
print(a)


from __future__ import division, print_function
from sys import stdin, stdout
import bisect
import math
import heapq

def modinv(n, p):
	return pow(n, p - 2, p)

def cin():
	return map(int, sin().split())

def ain():
	return list(map(int, sin().split()))

def sin():
	return input()

def inin():
	return int(input())
import math

def Divisors(n):
	l = []
	for i in range(1, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n // i == i:
				l.append(i)
			else:
				l.append(i)
				l.append(n // i)
	return l
q = []

def dfs(n, d, v, c):
	global q
	v[n] = 1
	x = d[n]
	q.append(n)
	j = c
	for i in x:
		if i not in v:
			f = dfs(i, d, v, c + 1)
			j = max(j, f)
	return j

def main():
	(n, l, r) = cin()
	f = (r - l + 1) // 3
	a = [f] * 3
	p = (r - l + 1) % 3
	for i in range(p):
		a[l % 3] += 1
		l += 1
	b = a[:]
	mod = 10 ** 9 + 7
	for i in range(1, n):
		x = a[0] * b[0] + a[1] * b[2] + a[2] * b[1]
		y = a[0] * b[1] + a[1] * b[0] + a[2] * b[2]
		z = a[0] * b[2] + a[1] * b[1] + a[2] * b[0]
		b = [x % mod, y % mod, z % mod]
	print(b[0])
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
import os, sys
from io import IOBase, BytesIO
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.getvalue())
			(self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			self.write = lambda s: self.buffer.write(s.encode('ascii'))
			self.read = lambda : self.buffer.read().decode('ascii')
			self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import sys

class ostream:

	def __lshift__(self, a):
		sys.stdout.write(str(a))
		return self
cout = ostream()
endl = '\n'

def readnumbers(zero=0):
	conv = ord if py2 else lambda x: x
	A = []
	numb = zero
	sign = 1
	i = 0
	s = sys.stdin.buffer.read()
	try:
		while True:
			if s[i] >= b'0'[0]:
				numb = 10 * numb + conv(s[i]) - 48
			elif s[i] == b'-'[0]:
				sign = -1
			elif s[i] != b'\r'[0]:
				A.append(sign * numb)
				numb = zero
				sign = 1
			i += 1
	except:
		pass
	if s and s[-1] >= b'0'[0]:
		A.append(sign * numb)
	return A
main()


import sys
import math
import collections
import heapq
import decimal
input = sys.stdin.readline
(n, l, r) = (int(i) for i in input().split())
mod = 1000000007
c1 = r // 3 - math.ceil(l / 3) + 1
c2 = (r - 1) // 3 - math.ceil((l - 1) / 3) + 1
c3 = (r - 2) // 3 - math.ceil((l - 2) / 3) + 1
dp = [[0, 0, 0] for i in range(n + 1)]
dp[1][0] = c1
dp[1][1] = c2
dp[1][2] = c3
for i in range(2, n + 1):
	dp[i][0] = (dp[i - 1][0] * c1 % mod + dp[i - 1][1] * c3 % mod + dp[i - 1][2] * c2 % mod) % mod
	dp[i][1] = (dp[i - 1][0] * c2 % mod + dp[i - 1][1] * c1 % mod + dp[i - 1][2] * c3 % mod) % mod
	dp[i][2] = (dp[i - 1][0] * c3 % mod + dp[i - 1][1] * c2 % mod + dp[i - 1][2] * c1 % mod) % mod
print(dp[n][0])


mod = 1000000007
dp = [[0] * 3 for i in range(200005)]
(n, l, r) = map(int, input().split())
(l3, r3) = (l % 3, r % 3)
k = r - l + 1
if l3 == r3:
	zero = k // 3
	one = k // 3
	two = k // 3
	if l3 == 0:
		zero += 1
	elif l3 == 1:
		one += 1
	else:
		two += 1
elif l3 == 0 and r3 == 1:
	(zero, one, two) = (k // 3 + 1, k // 3 + 1, k // 3)
elif l3 == 1 and r3 == 2:
	(zero, one, two) = (k // 3, k // 3 + 1, k // 3 + 1)
elif l3 == 2 and r3 == 0:
	(zero, one, two) = (k // 3 + 1, k // 3, k // 3 + 1)
else:
	(zero, one, two) = (k // 3, k // 3, k // 3)
(dp[1][0], dp[1][1], dp[1][2]) = (zero, one, two)
for i in range(2, n + 1):
	(dp[i][0], dp[i][1], dp[i][2]) = ((dp[i - 1][0] * zero + dp[i - 1][1] * two + dp[i - 1][2] * one) % mod, (dp[i - 1][0] * one + dp[i - 1][1] * zero + dp[i - 1][2] * two) % mod, (dp[i - 1][0] * two + dp[i - 1][1] * one + dp[i - 1][2] * zero) % mod)
print(dp[n][0])


import math
base = 10 ** 9 + 7
(n, l, r) = map(int, input().split())
dp = [[-1] * 3 for _ in range(n)]
dp[0][0] = math.floor(r / 3) - math.ceil(l / 3) + 1
dp[0][1] = math.floor((r - 1) / 3) - math.ceil((l - 1) / 3) + 1
dp[0][2] = math.floor((r - 2) / 3) - math.ceil((l - 2) / 3) + 1
for i in range(1, n):
	dp[i][0] = (dp[i - 1][0] * dp[0][0] + dp[i - 1][1] * dp[0][2] + dp[i - 1][2] * dp[0][1]) % base
	dp[i][1] = (dp[i - 1][1] * dp[0][0] + dp[i - 1][0] * dp[0][1] + dp[i - 1][2] * dp[0][2]) % base
	dp[i][2] = (dp[i - 1][1] * dp[0][1] + dp[i - 1][0] * dp[0][2] + dp[i - 1][2] * dp[0][0]) % base
print(dp[n - 1][0])


(n, l, r) = map(int, input().split())
d = [(r - i) // 3 - (l - i - 1) // 3 for i in [0, 1, 2]]
N = 10 ** 9 + 7
(a, b, c) = (d[0], d[1], d[2])
for _ in range(1, n):
	tmp1 = (a * d[0] + b * d[2] + c * d[1]) % N
	tmp2 = (a * d[1] + b * d[0] + c * d[2]) % N
	tmp3 = (a * d[2] + b * d[1] + c * d[0]) % N
	(a, b, c) = (tmp1, tmp2, tmp3)
print(a)


from collections import *
from math import *
(n, l, r) = map(int, input().split())
Mod = int(1000000000.0 + 7)
dp = [[0 for i in range(3)] for j in range(n + 1)]
m0 = floor(r / 3) - ceil(l / 3) + 1
m1 = floor((r - 1) / 3) - ceil((l - 1) / 3) + 1
m2 = floor((r - 2) / 3) - ceil((l - 2) / 3) + 1
dp[0][0] = 1
for i in range(1, n + 1):
	dp[i][0] = dp[i - 1][0] * m0 + dp[i - 1][1] * m2 + dp[i - 1][2] * m1
	dp[i][1] = dp[i - 1][1] * m0 + dp[i - 1][2] * m2 + dp[i - 1][0] * m1
	dp[i][2] = dp[i - 1][2] * m0 + dp[i - 1][0] * m2 + dp[i - 1][1] * m1
	for j in range(3):
		dp[i][j] %= Mod
print(dp[n][0])


def fu(l, r):
	return [r // 3 - (l - 1) // 3, (r - 1) // 3 - (l - 2) // 3, (r - 2) // 3 - (l - 3) // 3]
(n, l, r) = list(map(int, input().split()))
a = fu(l, r)
m = 10 ** 9 + 7
dp0 = [a[0]]
dp1 = [a[1]]
dp2 = [a[2]]
for i in range(1, n):
	x = (dp0[-1] * a[0] + dp1[-1] * a[2] + dp2[-1] * a[1]) % m
	y = (dp0[-1] * a[1] + dp1[-1] * a[0] + dp2[-1] * a[2]) % m
	z = (dp0[-1] * a[2] + dp1[-1] * a[1] + dp2[-1] * a[0]) % m
	dp0.append(x)
	dp1.append(y)
	dp2.append(z)
print(dp0[-1] % m)


def count(first, last):
	last -= fast
	last = last // d
	last += 1
	return last
(n, l, r) = list(map(int, input().split()))
rem = [1, 0, 0]
rem[0] = r // 3 - (l - 1) // 3
rem[1] = (r + 2) // 3 - (l - 1 + 2) // 3
rem[2] = (r + 1) // 3 - (l - 1 + 1) // 3
dp = [[0 for i in range(n)] for j in range(3)]
dp[0][0] = rem[0]
dp[1][0] = rem[1]
dp[2][0] = rem[2]
mod = 10 ** 9
mod += 7
for i in range(1, n):
	dp[0][i] = dp[0][i - 1] * rem[0] % mod
	dp[0][i] = (dp[0][i] + dp[1][i - 1] * rem[2] % mod) % mod
	dp[0][i] = (dp[0][i] + dp[2][i - 1] * rem[1] % mod) % mod
	dp[1][i] = (dp[1][i] + dp[0][i - 1] * rem[1] % mod) % mod
	dp[1][i] = (dp[1][i] + dp[1][i - 1] * rem[0] % mod) % mod
	dp[1][i] = (dp[1][i] + dp[2][i - 1] * rem[2] % mod) % mod
	dp[2][i] = (dp[2][i] + dp[0][i - 1] * rem[2] % mod) % mod
	dp[2][i] = (dp[2][i] + dp[2][i - 1] * rem[0] % mod) % mod
	dp[2][i] = (dp[2][i] + dp[1][i - 1] * rem[1] % mod) % mod
print(dp[0][-1])


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest
sys.setrecursionlimit(111111)
INF = 99999999999999999999999999999999

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

def main():
	mod = 1000000007
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	tc = 1
	for _ in range(tc):
		(n, l, r) = ria()
		total = r - l + 1
		k = total // 3
		(n0, n1, n2) = (k, k, k)
		for i in range(3):
			if (r - i) % 3 == (l + 2) % 3:
				break
			if (r - i) % 3 == 0:
				n0 += 1
			if (r - i) % 3 == 1:
				n1 += 1
			if (r - i) % 3 == 2:
				n2 += 1
		dp = [[0, 0, 0] for i in range(n + 1)]
		dp[1][0] = n0
		dp[1][1] = n1
		dp[1][2] = n2
		for i in range(2, n + 1):
			dp[i][0] = (dp[i - 1][0] * n0 + dp[i - 1][1] * n2 + dp[i - 1][2] * n1) % mod
			dp[i][1] = (dp[i - 1][0] * n1 + dp[i - 1][1] * n0 + dp[i - 1][2] * n2) % mod
			dp[i][2] = (dp[i - 1][0] * n2 + dp[i - 1][1] * n1 + dp[i - 1][2] * n0) % mod
		wi(dp[n][0])
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


M = 10 ** 9 + 7

def types(n):
	if n % 3 == 0:
		return (n // 3, n // 3, n // 3)
	elif n % 3 == 1:
		return (n // 3, n // 3 + 1, n // 3)
	return (n // 3, n // 3 + 1, n // 3 + 1)
(n, l, r) = map(int, input().split())
(nr0, nr1, nr2) = types(r)
(nl0, nl1, nl2) = types(l - 1)
(n0, n1, n2) = (nr0 - nl0, nr1 - nl1, nr2 - nl2)
(c0, c1, c2) = (1, 0, 0)
for _ in range(n):
	c0n = c0 * n0 + c1 * n2 + c2 * n1
	c1n = c0 * n1 + c1 * n0 + c2 * n2
	c2n = c0 * n2 + c1 * n1 + c2 * n0
	(c0, c1, c2) = (c0n % M, c1n % M, c2n % M)
print(c0)


def howmanyinlrneedk(l, r):
	n = r - l + 1
	L = [n // 3] * 3
	if n % 3 == 0:
		return L
	elif n % 3 == 1:
		L[l % 3] += 1
		return L
	else:
		L[l % 3] += 1
		L[(l + 1) % 3] += 1
		return L
[m, l, r] = [int(k) for k in input().split()]
[a, b, c] = howmanyinlrneedk(l, r)
A = [a]
B = [c]
C = [b]
for i in range(m - 1):
	A.append((a * A[0] + b * B[0] + c * C[0]) % (10 ** 9 + 7))
	B.append((c * A[0] + a * B[0] + b * C[0]) % (10 ** 9 + 7))
	C.append((b * A[0] + c * B[0] + a * C[0]) % (10 ** 9 + 7))
	A.pop(0)
	B.pop(0)
	C.pop(0)
print(A[-1])


mod = 10 ** 9 + 7
(n, l, r) = map(int, input().split())
dp = [[0] * 3 for i in range(n)]
rem0 = r // 3 - (l - 1) // 3
rem1 = (r + 2) // 3 - (l + 1) // 3
rem2 = (r + 1) // 3 - l // 3
dp[-1][0] = rem0
dp[-1][1] = rem1
dp[-1][2] = rem2
for i in range(n - 1, -1, -1):
	if i == n - 1:
		continue
	dp[i][0] = rem0 * dp[i + 1][0] % mod
	dp[i][0] = (dp[i][0] + rem1 * dp[i + 1][2]) % mod
	dp[i][0] = (dp[i][0] + rem2 * dp[i + 1][1]) % mod
	dp[i][1] = rem0 * dp[i + 1][1] % mod
	dp[i][1] = (dp[i][1] + rem1 * dp[i + 1][0]) % mod
	dp[i][1] = (dp[i][1] + rem2 * dp[i + 1][2]) % mod
	dp[i][2] = dp[i + 1][0] * rem2 % mod
	dp[i][2] = (dp[i][2] + rem0 * dp[i + 1][2]) % mod
	dp[i][2] = (dp[i][2] + rem1 * dp[i + 1][1]) % mod
print(dp[0][0])


(n, l, r) = list(map(int, input().split()))
dp = [[0] * 3 for i in range(n + 1)]
th = r // 3 - (l - 1) // 3
on = 0
tw = 0
iter = l
while iter % 3 != 0 and iter <= r:
	if iter % 3 == 1:
		on += 1
	elif iter % 3 == 2:
		tw += 1
	iter += 1
sector = r
while sector % 3 != 0 and sector > iter:
	if sector % 3 == 1:
		on += 1
	elif sector % 3 == 2:
		tw += 1
	sector -= 1
tw += max(th - 1, 0)
on += max(th - 1, 0)
cnt = [on, tw, th]
for i in range(1, n + 1):
	for k in range(3):
		if i == 1:
			dp[i][k] += cnt[k]
			dp[i][k] %= 1000000007
		else:
			if k == 1:
				dp[i][k] += dp[i - 1][k - 1] * on
				dp[i][k] += dp[i - 1][k] * th
				dp[i][k] += dp[i - 1][k + 1] * tw
				dp[i][k] %= 1000000007
			if k == 0:
				dp[i][k] += dp[i - 1][k + 1] * tw
				dp[i][k] += dp[i - 1][k] * th
				dp[i][k] += dp[i - 1][k + 2] * on
				dp[i][k] %= 1000000007
			if k == 2:
				dp[i][k] += dp[i - 1][k] * th
				dp[i][k] += dp[i - 1][k - 1] * on
				dp[i][k] += dp[i - 1][k - 2] * tw
				dp[i][k] %= 1000000007
print(dp[n][2])


(n, l, r) = map(int, input().split())
d = []
for i in range(3):
	d.append((r - i) // 3 - (l - i - 1) // 3)
mod = 10 ** 9 + 7
(a, b, c) = (d[0], d[1], d[2])
for _ in range(1, n):
	temp1 = (a * d[0] + b * d[2] + c * d[1]) % mod
	temp2 = (a * d[1] + b * d[0] + c * d[2]) % mod
	temp3 = (a * d[2] + b * d[1] + c * d[0]) % mod
	(a, b, c) = (temp1, temp2, temp3)
print(a)


from math import floor, ceil
(n, l, r) = map(int, input().split())
mod = int(1000000000.0 + 7)
zero = floor(r / 3) - ceil(l / 3) + 1
one = floor((r - 1) / 3) - ceil((l - 1) / 3) + 1
two = floor((r - 2) / 3) - ceil((l - 2) / 3) + 1
dp = [[0 for _ in range(3)] for _ in range(n + 1)]
(dp[1][0], dp[1][1], dp[1][2]) = (zero, one, two)
for i in range(2, n + 1):
	dp[i][0] = (dp[i - 1][0] * zero + dp[i - 1][1] * two + dp[i - 1][2] * one) % mod
	dp[i][1] = (dp[i - 1][0] * one + dp[i - 1][1] * zero + dp[i - 1][2] * two) % mod
	dp[i][2] = (dp[i - 1][0] * two + dp[i - 1][1] * one + dp[i - 1][2] * zero) % mod
print(dp[n][0])


stuff = list(map(int, input().rstrip().split()))
n = stuff[0]
l = stuff[1]
r = stuff[2]
mod = 10 ** 9 + 7
zeromods = r // 3 - (l - 1) // 3
onemods = (r - 1) // 3 - (l - 2) // 3
twomods = (r - 2) // 3 - (l - 3) // 3
combos = [[0, 0, 0] for i in range(n)]
combos[0] = [zeromods, onemods, twomods]
for i in range(1, n):
	combos[i][0] = (combos[i - 1][0] * zeromods + combos[i - 1][1] * twomods + combos[i - 1][2] * onemods) % mod
	combos[i][1] = (combos[i - 1][0] * onemods + combos[i - 1][1] * zeromods + combos[i - 1][2] * twomods) % mod
	combos[i][2] = (combos[i - 1][0] * twomods + combos[i - 1][1] * onemods + combos[i - 1][2] * zeromods) % mod
print(combos[-1][0])
combos


(n, l, r) = map(int, input().split())
a = [0] * 3
for d in range(3):
	a[d] += (r - d) // 3
	a[d] -= (l - 1 - d) // 3
M = 1000000007
b = [1, 0, 0]
for _ in range(n):
	c = [0] * 3
	for i in range(3):
		for j in range(3):
			c[(i + j) % 3] += b[i] * a[j] % M
			c[(i + j) % 3] %= M
	b = c
print(b[0])


(n, l, r) = map(int, input().split(' '))
m = 1000000007
dp = [[0] * 3 for _ in range(n + 1)]
nums_0 = r // 3 - (l - 1) // 3
nums_1 = (r - 1) // 3 - (l - 2) // 3
nums_2 = (r + 1) // 3 - l // 3
dp[1][0] = nums_0 % m
dp[1][1] = nums_1 % m
dp[1][2] = nums_2 % m
for j in range(2, n + 1):
	dp[j][0] = dp[j - 1][0] % m * (nums_0 % m) % m + dp[j - 1][1] % m * (nums_2 % m) % m + dp[j - 1][2] % m * (nums_1 % m) % m % m
	dp[j][1] = dp[j - 1][1] % m * (nums_0 % m) % m + dp[j - 1][2] % m * (nums_2 % m) % m + dp[j - 1][0] % m * (nums_1 % m) % m % m
	dp[j][2] = dp[j - 1][2] % m * (nums_0 % m) % m + dp[j - 1][0] % m * (nums_2 % m) % m + dp[j - 1][1] % m * (nums_1 % m) % m % m
print(dp[n][0] % m)


import math

def func():
	global x1, x2, x3
	x1 = x1 % p
	x2 = x2 % p
	x3 = x3 % p
	for i in range(n):
		for j in range(3):
			if i == 0:
				if j == 0:
					dp[i][j] = x3
				elif j == 1:
					dp[i][j] = x1
				else:
					dp[i][j] = x2
			else:
				if j == 0:
					dp[i][j] = x3 * dp[i - 1][0] + x1 * dp[i - 1][2] + x2 * dp[i - 1][1]
				elif j == 1:
					dp[i][j] = x3 * dp[i - 1][1] + x1 * dp[i - 1][0] + x2 * dp[i - 1][2]
				else:
					dp[i][j] = x3 * dp[i - 1][2] + x1 * dp[i - 1][1] + x2 * dp[i - 1][0]
				dp[i][j] = dp[i][j] % p
	return dp[n - 1][0]
(n, l, r) = tuple(map(int, input().split()))
p = 10 ** 9 + 7
if l == r:
	if n * l % 3 == 0:
		print(1)
	else:
		print(0)
else:
	x3 = math.floor(r / 3) - math.ceil(l / 3) + 1
	x1 = x3 - 1
	x2 = x3 - 1
	if l % 3 == 1:
		x1 += 1
		x2 += 1
	elif l % 3 == 2:
		x2 += 1
	if r % 3 == 1:
		x1 += 1
	elif r % 3 == 2:
		x1 += 1
		x2 += 1
	dp = [[-1, -1, -1] for i in range(n)]
	print(func() % p)


mod2 = 10 ** 9 + 7
mod = mod2 * 3
(n, l, r) = map(int, input().split())
l2 = l // 3 * 3
r2 = (r // 3 + 1) * 3 - 1
num0 = r2 - l2 + 1
num0 //= 3
nums = [num0, num0, num0]
for i in range(l2, l):
	nums[i % 3] -= 1
for i in range(r + 1, r2 + 1):
	nums[i % 3] -= 1
ar = [[0, 0, 0] for i in range(n)]
ar[0] = nums
for i in range(n - 1):
	for j in range(3):
		for z in range(3):
			ar[i + 1][(j + z) % 3] += ar[i][j] * nums[z]
			ar[i + 1][(j + z) % 3] %= mod2
print(ar[-1][0])


(n, l, r) = map(int, input().split())
a0 = [0 for i in range(n)]
a1 = [0 for i in range(n)]
a2 = [0 for i in range(n)]
k = r - l + 1
a0[0] = k // 3
a1[0] = k // 3
a2[0] = k // 3
if k % 3 == 1:
	if l % 3 == 1:
		a1[0] += 1
	elif l % 3 == 2:
		a2[0] += 1
	else:
		a0[0] += 1
elif k % 3 == 2:
	if l % 3 == 1:
		a1[0] += 1
		a2[0] += 1
	elif l % 3 == 2:
		a2[0] += 1
		a0[0] += 1
	else:
		a0[0] += 1
		a1[0] += 1
p0 = a0[0]
p1 = a1[0]
p2 = a2[0]
for i in range(1, n):
	a0[i] = (a0[i - 1] * p0 + a1[i - 1] * p2 + a2[i - 1] * p1) % (10 ** 9 + 7)
	a1[i] = (a0[i - 1] * p1 + a1[i - 1] * p0 + a2[i - 1] * p2) % (10 ** 9 + 7)
	a2[i] = (a0[i - 1] * p2 + a1[i - 1] * p1 + a2[i - 1] * p0) % (10 ** 9 + 7)
print(a0[n - 1])


(n, l, r) = list(map(int, input().strip().split()))
mod = 1000000007
x = r - l + 1
t = x // 3
if x % 3 == 0:
	(m0, m1, m2) = (t, t, t)
elif x % 3 == 1:
	(m0, m1, m2) = (t + 1, t, t)
elif x % 3 == 2:
	(m0, m1, m2) = (t + 1, t + 1, t)
if l % 3 == 0:
	(m0, m1, m2) = (m0, m1, m2)
elif l % 3 == 1:
	(m1, m2, m0) = (m0, m1, m2)
elif l % 3 == 2:
	(m2, m0, m1) = (m0, m1, m2)
dp = [[0 for j in range(3)] for i in range(n)]
dp[0][0] = m0
dp[0][1] = m1
dp[0][2] = m2
for i in range(1, n):
	dp[i][0] = (dp[i - 1][0] * m0 % mod + dp[i - 1][1] * m2 % mod + dp[i - 1][2] * m1 % mod) % mod
	dp[i][1] = (dp[i - 1][0] * m1 % mod + dp[i - 1][1] * m0 % mod + dp[i - 1][2] * m2 % mod) % mod
	dp[i][2] = (dp[i - 1][0] * m2 % mod + dp[i - 1][1] * m1 % mod + dp[i - 1][2] * m0 % mod) % mod
print(dp[n - 1][0])


m = 10 ** 9 + 7
(n, l, r) = (int(x) for x in input().split())
t = r - l + 1
tm = None
if (r + 1) % 3 == l % 3:
	tm = (t // 3,) * 3
elif ((r + 1) % 3 - l % 3) % 3 == 1:
	a = [0, 0, 0]
	a[l % 3] = 1
	tm = (t // 3 + a[0], t // 3 + a[1], t // 3 + a[2])
else:
	a = [0, 0, 0]
	a[l % 3] = 1
	a[r % 3] = 1
	tm = (t // 3 + a[0], t // 3 + a[1], t // 3 + a[2])
ans0 = ans1 = ans2 = 0
(ans0, ans1, ans2) = tm
(ans0o, ans1o, ans2o) = tm
for i in range(n - 1):
	ans0n = (ans0o * ans0 + ans2o * ans1 + ans1o * ans2) % m
	ans1n = (ans0o * ans1 + ans1o * ans0 + ans2o * ans2) % m
	ans2n = (ans0o * ans2 + ans1o * ans1 + ans2o * ans0) % m
	(ans0o, ans1o, ans2o) = (ans0n, ans1n, ans2n)
print(ans0o % m)


mod = 10 ** 9 + 7
(n, l, r) = map(int, input().split())
if l == r:
	if n % 3 == 0:
		print(1)
	else:
		print(0)
	exit()
dp = [[0, 0, 0] for i in range(n)]
dp[0][0] = r // 3 - l // 3
dp[0][1] = (r - 1) // 3 - (l - 1) // 3
dp[0][2] = (r - 2) // 3 - (l - 2) // 3
dp[0][l % 3] += 1
for i in range(1, n):
	dp[i][0] = (dp[i - 1][1] * dp[0][2] + dp[i - 1][0] * dp[0][0] + dp[i - 1][2] * dp[0][1]) % mod
	dp[i][1] = (dp[i - 1][1] * dp[0][0] + dp[i - 1][0] * dp[0][1] + dp[i - 1][2] * dp[0][2]) % mod
	dp[i][2] = (dp[i - 1][0] * dp[0][2] + dp[i - 1][2] * dp[0][0] + dp[i - 1][1] * dp[0][1]) % mod
print(dp[-1][0] % mod)


import math
(n, l, r) = map(int, input().split())
b = [0, 0, 0]
b[l % 3] = (r - l + 3) // 3
b[(l + 1) % 3] = (r - l + 2) // 3
b[(l + 2) % 3] = (r - l + 1) // 3
mod = 10 ** 9 + 7
dp = [[0 for i in range(3)] for j in range(n + 1)]
dp[0][0] = 1
dp[0][1] = 0
dp[0][2] = 0
for i in range(1, n + 1):
	dp[i][0] = (b[0] * dp[i - 1][0] % mod + b[1] * dp[i - 1][2] % mod + b[2] * dp[i - 1][1] % mod) % mod
	dp[i][1] = (b[0] * dp[i - 1][1] % mod + b[1] * dp[i - 1][0] % mod + b[2] * dp[i - 1][2] % mod) % mod
	dp[i][2] = (b[0] * dp[i - 1][2] % mod + b[1] * dp[i - 1][1] % mod + b[2] * dp[i - 1][0] % mod) % mod
print(dp[n][0] % mod)