import sys
n_l_r  = sys.stdin.readline().strip().split(" ")
n , l , r = int(n_l_r[0]),int(n_l_r[1]),int(n_l_r[2])
dp = [0,0,0]
for i in range(l,r+1):
    if(i%3==0):
        dp[0] += 1
    elif(i%3==1):
        dp[1] += 1
    else:
        dp[2] += 1
kdp = [[0 for i in range(3)] for j in range(n)]
kdp[0][0] = dp[0]
kdp[0][1] = dp[1]
kdp[0][2] = dp[2]
kdp[1][0] = kdp[0][0]*kdp[0][0] + 2* kdp[0][1]* kdp[0][2]
kdp[1][1] =  kdp[0][0]*kdp[0][1] + kdp[0][2]*kdp[0][2] + kdp[0][1]*kdp[0][0]
kdp[1][2] =  kdp[0][0]*kdp[0][2] + kdp[0][2]*kdp[0][0] + kdp[0][2]*kdp[0][0]
for t in range(2,n):
    kdp[t][0] = dp[0]*kdp[t-1][0] + dp[1]*kdp[t-1][2] + dp[2]*kdp[t-1][1]
    kdp[t][1] = dp[0]*kdp[t-1][1] + dp[1]*kdp[t-1][0] + dp[2]*kdp[t-1][2]
    kdp[t][2] = dp[0]*kdp[t-1][2] + dp[1]*kdp[t-1][1] + dp[2]*kdp[t-1][0]

if(n==1):
    print(dp[0])
elif(n==2):
    print(2*dp[1]*dp[2]+dp[0]*dp[0])
elif(n==3):
    print(dp[0]*dp[0]*dp[0] + 3*dp[0]*(2*dp[1]*dp[2]) + dp[1] + dp[2])
else:
    print(kdp[n-1][0])

import sys
import math

n_k = sys.stdin.readline().strip().split(" ")
n, k = int(n_k[0]), int(n_k[1])
str_in = sys.stdin.readline().strip().split(" ")
list_in = []
for i in range(n):
    list_in.append(int(str_in[i]))
mod_res = [0 for i in range(k)]
res = 1
for l in list_in:
    mod_res[l % k] += 1
if (k == 1):
    print(1 + n)
else:
    if (k % 2 == 0):
        res *= (mod_res[0] + 1) * (mod_res[k // 2] + 1)
    else:
        res *= (mod_res[0] + 1)

    for i in range(1, (k + 1) // 2):
        if (mod_res[i] == 0 and mod_res[k - i] == 0):
            res *= 1
            res = res % 1000000007
        elif (mod_res[i] == 0):
            res *= int(math.pow(2, mod_res[k - i]))
            res = res % 1000000007
        elif (mod_res[k - i] == 0):
            res *= int(math.pow(2, mod_res[i]))
            res = res % 1000000007
        else:
            res *= int(math.pow(2, mod_res[i]) + math.pow(2, mod_res[k - i]) - 1)
            res = res % 1000000007
    print(res)