Ayoub had an array a of integers of size n and this array had two interesting properties: 

  * All the integers in the array were between l and r (inclusive). 
  * The sum of all the elements was divisible by 3. 



Unfortunately, Ayoub has lost his array, but he remembers the size of the array n and the numbers l and r, so he asked you to find the number of ways to restore the array. 

Since the answer could be very large, print it modulo 10^9 + 7 (i.e. the remainder when dividing by 10^9 + 7). In case there are no satisfying arrays (Ayoub has a wrong memory), print 0.

Input

The first and only line contains three integers n, l and r (1 ≤ n ≤ 2 ⋅ 10^5 , 1 ≤ l ≤ r ≤ 10^9) — the size of the lost array and the range of numbers in the array.

Output

Print the remainder when dividing by 10^9 + 7 the number of ways to restore the array.

Examples

Input


2 1 3


Output


3


Input


3 2 2


Output


1


Input


9 9 99


Output


711426616

Note

In the first example, the possible arrays are : [1,2], [2,1], [3, 3].

In the second example, the only possible array is [2, 2, 2].
import random                    #libreria_necesaria_para_generar_numeros_de_forma_aleatoria
from math import floor, ceil     #librerias_ncesarias_para_realizar_los_calculos_necesarios


# __________________________________________________#
# brute force solution_____________________________#
def solve_1(n, l, r, mod):
    c = [0] * n
    return combination(n, l, r, c, 0, [0] * 1, 0, mod)      #creando_todas_las_combinaciones

def combination(n, l, r, c, pos, count, sum, mod):
    if (pos == n):      #cuando_la_combinacion_ya_tiene_el_tamano_requerido_no_se_agregan...
                        #mas_elementos_y_se_analiza_la_suma_total_de_esta
        if sum % 3 == 0:     #si_la_suma_es_divisible_por_3_se_suma_una_combinacion_valida
            count[0] = (count[0] + 1) % mod
        #print(c)   #descomentar_para_imprimir_las_combinaciones
        return

    for i in range(l, r + 1):
        c[pos] = i      #agregando_elemento_a_la_combinacion
        combination(n, l, r, c, pos + 1, count, sum + i, mod)    #llamado_recursivo
    return int(count[0])


# __________________________________________________#
# solution_________________________________________#
def solve_2(n, l, r, mod):
    c0, c1, c2 = [count(l, r, int(i)) for i in range(0, 3)]    #calculando_c0_c1_c2
    d = [0] * 3
    d[0], d[1], d[2] = c0, c1, c2    #la_cantidad_de_arrays_de_tamano_1_para_los_3_restos...
                                     #es_exactamente_c0_c1_y_c2_respectivamente

    for i in range(1, n):        #iterando_por_todos_los_tamanos_hasta_n
        m0 = ((d[0] * c0) + (d[2] * c1) + (d[1] * c2)) % mod          #cantidad_de_arrays_de_tamano_i_cuya_suma_deja_resto_0_con_3
        m1 = ((d[1] * c0) + (d[0] * c1) + (d[2] * c2)) % mod          #cantidad_de_arrays_de_tamano_i_cuya_suma_deja_resto_1_con_3
        m2 = ((d[1] * c1) + (d[0] * c2) + (d[2] * c0)) % mod          #cantidad_de_arrays_de_tamano_i_cuya_suma_deja_resto_2_con_3
        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    #cantidad_de_elementos_que_dejan_resto...
                                                                         #remainder_con_3_en_el_intervalo_[l,r]


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


# __________________________________________________#
# random cases tester______________________________#
def random_cases():
    mod = (10 ** 9 + 7)
    case = [0] * 3
    case_generator(case)   #genarando_caso_random
    print('Case: \n' + 'n = ' + str(case[0]) + '  ' + 'l = ' + str(case[1]) + '  ' + 'r = ' + str(case[2]))
    #print(solve_1(case[0], case[1], case[2], mod))   #solucion_fuerza_bruta
    print(solve_2(case[0], case[1], case[2], mod))    #solucion_eficiente
    return

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


# __________________________________________________#
# tester___________________________________________#
def tester():
    for i in range(1, 5):       #cantidad_de_casos_que_se_desean_probar
        mod = (10 ** 9 + 7)
        case = [0] * 3
        case_generator(case)    #generando_caso_aleatorio
        s1 = solve_1(case[0], case[1], case[2], mod)     #solucion_fuerza_bruta
        s2 = solve_2(case[0], case[1], case[2], mod)     #solucion_eficiente

        print('Case ' + str(i) + ':\n' + 'n = ' + str(case[0]) + '  ' + 'l = ' +
              str(case[1]) + '  ' + 'r = ' + str(case[2]))
        print('solucion fuerza bruta : ' + str(s1))    #solucion_fuerza_bruta
        print('solucion eficiente : ' + str(s2))       #solucion_eficiente
        if (s1 == s2):     #verificando_si_las_soluciones_coinciden
            print('Accepted\n')
        else:
            print('Wrong Answer\n')
    return


main()               #entrada_de_casos_por_consola
#random_cases()      #casos_random
#tester()            #comprobar_solucion_eficiente_contra_solucion_fuerza_bruta
