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

#sys.stdin = open('input.txt', 'r')
#sys.stdout = open('output.txt', 'w')

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  # or / in Python 2


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
# T = int(stdin.readline())
for _ in range(T):
    n, l, r = list(map(int, stdin.readline().split()))
    # s1 = list(stdin.readline().strip('\n'))
    # n = int(stdin.readline())
    #n, m, x = list(map(int, stdin.readline().split()))
    # s = str(stdin.readline().strip('\n'))
    # s2 = list(stdin.readline().strip('\n'))
    # a = 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])
    # print(dp)
