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 java.util.*;
public class Solution
{
    static long dp[][];
    static long ways(int a , int b , int c , int pos , int sum , int n)
    {
        if(pos == n)
        {
            if(sum == 0)
            return 1;
            
            return 0;
        }
        
        long p = 1000000007;
        
        if(dp[pos][sum] != -1)
        return dp[pos][sum];
        
        dp[pos][sum] = (a%p*ways(a , b , c , pos + 1 , sum , n))%p + (b%p*ways(a , b , c , pos + 1 , (sum + 1)%3 , n))%p
                        + (c%p*ways(a , b , c , pos + 1 , (sum + 2)%3 , n))%p;
                        
                        return dp[pos][sum] %p;
    }
    public static void main(String []args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int l = sc.nextInt();
        int r = sc.nextInt();
        
        dp = new long[n][3];
        for(int i = 0 ; i < n ; i++)
        {
            for(int j = 0 ; j < 3 ; j++)
            {
                dp[i][j] = -1;
            }
        }
        int a = 0 , b = 0 , c = 0;
        int x = 0 , y = 0;
        if(l % 3 == 0)
        x = l;
        
        else if((l+1) % 3 == 0)
        x = l+1;
        
        else
        x = l+2;
        
        
        if(r%3 == 0)
        y = r;
        
        else if((r - 1)%3 == 0)
        y = r - 1;
        
        else
        y = r-2;
        
        if(x <= y)
        a = (y-x)/3 + 1;
        
        else
        a = 0;
        
        
          if(l % 3 == 1)
        x = l;
        
        else if((l+1) % 3 == 1)
        x = l+1;
        
        else
        x = l+2;
        
        
        if(r%3 == 1)
        y = r;
        
        else if((r - 1)%3 == 1)
        y = r - 1;
        
        else
        y = r-2;
        
        if(x <= y)
        b = (y-x)/3 + 1;
        
        else
        b = 0;
        
        c = (r - l + 1) - (a + b);
        
        System.out.println(ways(a , b , c , 0 , 0 , n));
        
    }
}