matrix exponentiation

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll nmax=1e9+7;

vector<vector<ll>> mat_mul(vector<vector<ll>> a, vector<vector<ll>> b, ll mod){
    ll n=a.size();
    vector<vector<ll>> res(n,vector<ll>(n));
    for (ll i=0; i<n; i++){
        for (ll j=0; j<n; j++){
            for (ll k=0; k<n; k++){
                res[i][j]+=a[i][k]*b[k][j];
                res[i][j]%=mod;
            }
        }
    }
    return res;
}
vector<vector<ll>> mat_pow(vector<vector<ll>> a, ll x, ll mod){
    ll n=a.size();
    vector<vector<ll>> res(n,vector<ll>(n));
    for (ll i=0; i<n; i++) res[i][i]=1;
    while(x>0){
        if (x&1) res=mat_mul(res,a,mod);
        a = mat_mul(a,a,mod);
        x>>=1;
    }
    return res;
}
int main()
{
    vector<vector<ll>> ans(2,vector<ll>(2));
    ans[0][0]=19;
    ans[0][1]=6;
    ans[1][0]=7;
    ans[1][1]=20;
    ll n;
    cin>>n;
    ans=mat_pow(ans,n,nmax);
    cout<<ans[0][0];
}