#include<bits/stdc++.h>
using namespace std;

// #define int long long

const int P=1e9+7;
const int mod = 1e9 + 7;

int s;

struct Matrix {
    int a[5][5];

    Matrix(int _t=0){
        for(int i=0;i<s;i++)
            for(int j=0;j<s;j++)
                a[i][j]=(i==j)*_t;
    }
};

Matrix operator *(const Matrix &a,const Matrix &b)
{
    Matrix c;
    for(int i=0;i<s;i++)
        for(int k=0;k<s;k++)
            for(int j=0;j<s;j++)
                c.a[i][j]=(c.a[i][j]+1ll*a.a[i][k]*b.a[k][j])%P;
    return c;
}

Matrix qpow(Matrix a,int b)
{
    Matrix ret(1);
    while(b)
    {
        if(b&1)
            ret=ret*a;
        b>>=1;
        a=a*a;
    }
    return ret;
}

int qpow(int a,int b)
{
    int ret=1;
    while(b)
    {
        if(b&1)
            ret=1ll*ret*a%P;
        b>>=1;
        a=1ll*a*a%P;
    }
    return ret;
}


vector<int> bm(vector<int> s) {
    int n = s.size() , L = 0 , m = 0;
    vector<int> C(n) , B(n) , T ;
    C[0] = B[0] = 1;

    int b = 1;
    for(int i = 0;i < n;i++) {
        ++m ;
        int d = s[i] % mod;
        for(int j = 1;j <= L;j++) d = (d + 1LL * C[j] * s[i - j]) % mod;
        if(!d) continue ;
        T = C ;
        int coef = 1LL * d * qpow(b , mod - 2) % mod;
        for(int j = m ; j < n;j++) C[j] = (C[j] - 1LL * coef * B[j - m]%mod + mod) % mod;
        if(2 * L > i) continue ;
        L = i + 1 - L;
        B = T ;
        b = d ;
        m = 0;
    }
    C.resize(L + 1) ;
    C.erase(C.begin()) ;
    for(auto &x : C) x = (mod - x) % mod;
    return C ;
}
/// 3*f(n-1) + (-2)*f(n-2) + f(n-3) + (-1)*f(n-4) + 0 * f(n - 5);
/// @return 
int f[] = {0,1,2,6,16,36,80,178,394,870,1920,4236,9344};
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    // vector<int> v({1,2,6,16,36,80,178,394,870,1920,4236,9344});
    // auto coe = bm(v) ;
    // for(auto x : coe) cout << x <<' ' ; cout << '\n';
    // const int N = 1e9 ;
    // for(int i = 13;i <= N;i++) {
    //     int p = i % 13 ;
    //     f[p] = (( (3LL * f[(p + 12) % 13] + (-2LL)*f[(p + 11) % 13] + f[(p + 10) % 13] + (-1LL) * f[(p + 9) % 13]) % mod ) + mod ) % mod;
    //     if(i == N) {
    //         cout << f[p] << '\n';
    //     }
    // }
    int n;
    while(cin>>n)
    {
        if(n<=12)
            cout<<f[n]<<"\n";
        else
        {
            s = 4;
            Matrix A, B;
            A.a[0][0] = 870, A.a[0][1] = 1920, A.a[0][2] = 4236, A.a[0][3] = 9344;
            B.a[0][3] = P - 1;
            B.a[1][3] = 1; B.a[1][0] = 1;
            B.a[2][3] = P - 2; B.a[2][1] = 1;
            B.a[3][3] = 3; B.a[3][2] = 1;
            A = A * qpow(B, n - 9);
            cout << A.a[0][0] << "\n";
        }
    }

    return 0;
}