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.io.*;
import java.util.*;
import java.lang.*;
import java.awt.*;
import java.awt.geom.*;
import java.math.*;
import java.text.*;
import java.math.BigInteger.*;
import java.util.Arrays; 

public class   cmorbust3
{
  BufferedReader in;
  StringTokenizer as;
  long nums[],nums2[];
  int mod = 1000000007;
  ArrayList < Integer > [] ar;
  
  public static void main (String[] args)
  {
    new cmorbust3  ();
  }
  
  
  public int GCD(int a, int b) {
    if (b==0) return a;
    return GCD(b,a%b);
  }
  
  public cmorbust3  ()
  {
    try
    {
      
      in = new BufferedReader (new InputStreamReader (System.in));
      
      long a = nextInt();
      long b = nextInt();
      long c = nextInt();
      nums  = new long [3];
      nums2 = new long [3];
      if(c - b < 10)
      {
        for(long x = b;x<=c;x++)
        {
          nums[(int)x%3] ++;
        }
      }
      else
      {
        for(b = b;b<=c;b++)
        {
          if(b % 3 == 0)
            break;
          nums[(int)(b%3)]++;
        }
        for(c = c;c>=b;c--)
        {
          if(c %3 == 2)
            break;
          nums[(int)(c%3)]++;
        }
        long temp = (((c-b)+1)/3);
        nums[0] += temp;
        nums[1] += temp;
        nums[2] += temp;
      }
      for(int x = 0;x<3;x++)
      {
       // System.out.print(nums[x] + " " );
      }
    //  System.out.println();
      nums2[0]= nums[0];
      nums2[1]= nums[1];
      nums2[2]= nums[2];
      for(long xx = 1;xx<a;xx++)
      {
        long a1 = nums2[0];
        long a2 = nums2[1];
        long a3 = nums2[2];
        nums2 = new long [3];
        for(int x = 0;x<3;x++)
        {
          nums2[x] += a1 *nums[x];
          nums2[(x+1)%3] += a2 * nums[x];
          nums2[(x+2)%3] += a3 * nums[x];
          for(int x1 = 0;x1<3;x1++)
          {

            nums2[x1] = nums2[x1] % mod;
          }

        }
        
      }
      System.out.println(nums2[0] % mod);
      
      
    }
    
    catch(IOException e)
    {
      
    }
  }
  
  
  
  
  
  
  
  String next () throws IOException
  {
    while (as == null || !as.hasMoreTokens ())
    {
      as = new StringTokenizer (in.readLine ().trim ());
    }
    
    
    return as.nextToken ();
  }
  
  
  
  long nextLong () throws IOException
  {
    return Long.parseLong (next ());
  }
  
  
  int nextInt () throws IOException
  {
    return Integer.parseInt (next ());
  }
  
  
  double nextDouble () throws IOException
  {
    return Double.parseDouble (next ());
  }
  
  
  String nextLine () throws IOException
  {
    return in.readLine ().trim ();
  }
}