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: interview

Starter code:

Solutions:
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])




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



#      
import collections, atexit, math, sys, bisect 

sys.setrecursionlimit(1000000)
def getIntList():
    return list(map(int, input().split()))    

try :
    #raise ModuleNotFoundError
    import numpy
    def dprint(*args, **kwargs):
        #print(*args, **kwargs, file=sys.stderr)
        # in python 3.4 **kwargs is invalid???
        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())     #idle 中不会执行 atexit
    
N, L, R = getIntList()
#print(N)

base = 10 ** 9 + 7
#  1 2 3 4 5
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])






n,l,r=map(int,input().split())
dp=[[0]*3 for _ in range(n+5)]

mod = 10**9+7
rcnt=[0]*3

ll,rr=l//3+1,r//3
for i in range(3):
    rcnt[i]+=rr-ll

if l%3==0:
    rcnt[0]+=1
    rcnt[1]+=1
    rcnt[2]+=1
elif l%3==1:
    rcnt[1]+=1
    rcnt[2]+=1
else:
    rcnt[2]+=1

if r%3==0:
    rcnt[0]+=1
elif r%3==1:
    rcnt[0]+=1
    rcnt[1]+=1
else:
    rcnt[0]+=1
    rcnt[1]+=1
    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])

import copy
import itertools
import string

###

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

###

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

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

###

M = 10**9+7

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


core()



































































































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])
#print(dp)
#print(modz,modo,modt)


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])
    
    


# -*- coding: utf-8 -*-
# @Time    : 2019/1/20 20:36
# @Author  : LunaFire
# @Email   : gilgemesh2012@gmail.com
# @File    : C. Ayoub and Lost Array.py


def main():
    n, l, r = list(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])


def __starting_point():
    main()

__starting_point()

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))
    else:
        if 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()


#! usr/bin/env python
# -*- coding: utf-8 -*-


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

n, l, r = list(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])


#!/usr/bin/env python
# coding: utf-8

# In[22]:


stuff=list(map(int, input().rstrip().split()))


# In[23]:


n=stuff[0]
l=stuff[1]
r=stuff[2]

mod=10**9+7


# In[24]:



zeromods=r//3-(l-1)//3

onemods=(r-1)//3-(l-2)//3

twomods=(r-2)//3-(l-3)//3


# In[25]:


combos=[[0,0,0] for i in range(n)]


# In[26]:


combos[0]=[zeromods,onemods,twomods]


# In[28]:


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])    


# In[29]:


combos


# In[ ]:






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])

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]
#print(d0[0], d1[0], d2[0])
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])


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 = [int(i) for i in input().split()]

#dp = [[0 for i in range(3)] for j in range(3)]

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 = [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)


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
#print(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])

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]
#dp[ost][n] = dp[0][n - 1] * mmm[ost] + dp[1][n - 1] * mmm[(ost - 1) % 3] + dp[2][n - 1] * mmm[(ost - 2) % 3]
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))

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 = []
        # Remainder is 0
        # 0 + 0 / 1 + 2 / 2 + 1
        newRem.append(
            ((nums[0] * rem[0]) % mod +
             (nums[1] * rem[2]) % mod +
             (nums[2] * rem[1]) % mod) % mod
        )
        # Remainder is 1
        # 0 + 1 / 1 + 0 / 2 + 2
        newRem.append(
            ((nums[0] * rem[1]) % mod +
             (nums[1] * rem[0]) % mod +
             (nums[2] * rem[2]) % mod) % mod
        )
        # Remainder is 2
        # 0 + 2 / 1 + 1 / 2 + 0
        newRem.append(
            ((nums[0] * rem[2]) % mod +
             (nums[1] * rem[1]) % mod +
             (nums[2] * rem[0]) % mod) % mod
        )
        rem = newRem[:]
    print(rem[0])

main()
    


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] )

#assert t == tm1+tm2+tm3
#print(tm)

ans0 = ans1 = ans2 = 0 #for n = 0
ans0, ans1, ans2 = tm #for n = 1
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, ans1o, ans2o )
#ans3 = t**n

print(ans0o%m)

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

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]

# print(k)
for idx in range(1, n, 1):
    # print(idx)
    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)

print(f[n-1][0] % MOD)

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])