1105C - Ayoub and Lost Array - CodeForces Solution

//har har mahadev
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define p pair
#define pll pair<ll,ll>
#define vpll vector<pair<ll,ll>>
#define ull unsigned long long int
#define vll vector<ll>
#define vvll vector<vector<ll>>
#define rep(i,a,b) for(i=a;i<=b;i++)
#define repr(i,a,b) for(i=a;i>=b;i--)
#define all(v) v.begin() , v.end()
#define rall(v) v.rbegin(),v.rend()
#define ff first
#define ss second
#define pb push_back
typedef unsigned long long int ulli;
template<typename T> istream& operator>>(istream& in, vector<T>& a) {for (auto &x : a) in >> x; return in;};
template<typename T> ostream& operator<<(ostream& out, vector<T>& a) {for (auto &x : a) out << x << ' '; return out;};

template<typename T1, typename T2> ostream& operator<<(ostream& out, const p<T1, T2>& x) {return out << x.ff << ' ' << x.ss;}
template<typename T1, typename T2> istream& operator>>(istream& in, p<T1, T2>& x) {return in >> x.ff >> x.ss;}

ll powermod(ll a, ll b, ll m)
{
    if (b == 0) return 1;
    ull k = powermod(a, b / 2, m);
    k = k * k;
    k %= m;
    if (b & 1) k = (k * a) % m;
    return k;
}
ll inverse(ll b, ll mod) {
    return powermod(b, mod - 2, mod);
}
// nCr with modulus
long long int mod = 1e9 + 7;
// ll factorial(ll n, ll r){
//     if(r==0||r==n) return 1;

//     // dp[n][r]=
//     return (factorial (n-1,r,dp)%mod + factorial (n-1,r-1,dp)%mod)%mod;

// }
ll kadane( vll arr, ll n) {

    ll max_end = 0;
    ll mx = LLONG_MIN;

    for (ll i = 0; i < n; i++) {
        max_end += arr[i];
        if (mx < max_end) {
            mx = max_end;
        }
        if (max_end < 0) {
            max_end = 0;
        }
    }
    return mx;
}
// Prime test for large numbers

bool isPrime(ull n, int iter = 10)
{
    if (n < 4) return n == 2 || n == 3;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 0; i < iter; i++)
    {
        ull a = 2 + rand() % (n - 3);
        if (powermod(a, n - 1, n) != 1) return false;
    }
    return true;
}
bool isval(int i, int j, int n, int m) {
    if (i < 0 || j < 0 || i >= n || j >= m) return false;
    return true;
}
void dfs(ll node, vvll &adj, vll &vis) {
    vis[node] = 1;
    for (auto it : adj[node]) {
        if (vis[node] == 0) dfs(node, adj, vis);
    }
}
const ll N = 1e7;
// vll prime(N + 1, -1);
// void sieve(ll n)
// {


//     // for (ll i = 0; i <= n; i++) prime[i] = -1;
//     prime[0] = 0;
//     prime[1] = 0;
//     ll m = sqrt(n);

//     for (ll p = 2; p <= m; p++)
//     {

//         //
//         if (prime[p] == -1)
//         {
//             // prime[p] = p;
//             for (ll i = p * p; i <= n; i += p)
//                 prime[i] = p;

//         }
//     }
//     return ;

// }
ll findLowerBound(vector<pair<ll, ll> >& arr,
                  pair<ll, ll>& p1)
{
    // Given iterator points to the
    // lower_bound() of given pair
    auto low = upper_bound(arr.begin(), arr.end(), p1);

    return low - arr.begin();
}
ll maxvec(vll &v) {
    ll mx  = LLONG_MIN;
    ll i;
    rep(i, 0, v.size() - 1) mx = max(v[i], mx);
    return mx;
}
ll minvec(vll &v) {
    ll mn  = LLONG_MAX;
    ll i;
    rep(i, 0, v.size() - 1) mn = min(v[i], mn);
    return mn;
}
ll sumvec(vll &v) {
    ll sum = 0;
    ll i;
    rep(i, 0, v.size() - 1) sum += v[i];
    return sum;
}
ll func(ll i, ll j) {
    if (i % j == 0) return i / j;
    return (i / j) + 1;
}
string mini(vll &num, ll a) {
    string res = "";
    for (ll i = 0; i < 10; i++) {
        if (i != a)
            for (ll j = 0; j < num[i]; j++) res += i + '0';
        else for (ll j = 0; j < num[i] - 1; j++) res += i + '0';
    }
    return res;
}

void bits(ll n, vll&v) {
    ll k = 0;
    while (n > 0) {
        v[k++] = n % 2;
        n /= 2;
    }
}


void yahapekrege() {
    ll n, l, r;
    cin >> n >> l >> r;
    vll v(3, 0);
    for (ll i = l; i <= min(l + 2, r); i++) {
        v[i % 3] = (r - i) / 3 + 1;
    }
    // cout << v;
    vvll dp(n + 1, vll(3, 0));
    dp[0][0] = 1;
    for (ll i = 1; i <= n; i++) {
        for (ll j = 0; j < 3; j++) {
            for (ll k = 0; k < 3; k++) {
                dp[i][(j + k) % 3] += dp[i - 1][k] * v[j];
                dp[i][(j + k) % 3] %= mod;
            }

        }
        for (ll j = 0; j < 3; j++) dp[i][j] %= mod;
    }
    // cout << dp[1][0];
    cout << dp[n][0];
}
int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);


    // int t;
    // cin >> t;
    // // int a = 1;
    // while (t--) {
    // cout<<"Case #"<<a<<": ";

    yahapekrege();
    // a++;
    cout << endl;
    // }
    return 0;
}