Anderson Franz

#include <bits/stdc++.h>
#define REP(i,n) for (int i = 1; i <= n; i++)
using namespace std;

typedef int64_t ll;
typedef vector<vector<ll> > matrix;
const ll MOD = 13371337;
const ll K = 4;


//SOLUÇÃO DA RECORRÊNCIA F(N) = F(N-2)+ (2^N*N^2)

matrix mul(matrix A, matrix B){
    matrix C(K+1, vector<ll>(K+1));
    REP(i, K) REP(j, K) REP(k, K){
        C[i][j] = (C[i][j]%MOD + (A[i][k]%MOD) * (B[k][j] < 0 ? B[k][j]%-MOD : B[k][j]%MOD)) % MOD;
    }
    return C;
}

matrix pow(matrix A, ll p){
    if (p == 1)
        return A;
    if (p % 2)
        return mul(A, pow(A, p-1));
    matrix X = pow(A, p/2);
    return mul(X, X);
}

ll fib(ll N,ll resp[]){
    vector<ll> F1(K+1);
    F1[1] = resp[0];
    F1[2] = resp[1];
    F1[3] = resp[2];
    F1[4] = resp[3];

    matrix T(K+1, vector<ll>(K+1));
    T[1][1] = 4ll, T[1][2] = -4ll, T[1][3] = 0ll, T[1][4] = 1ll;
    T[2][1] = 1ll, T[2][2] = 0ll, T[2][3] = 0ll, T[2][4] = 0ll;
    T[3][1] = 32ll, T[3][2] = -32ll, T[3][3] = 1ll, T[3][4] = 8ll;
    T[4][1] = 0ll, T[4][2] = 0ll, T[4][3] = 0ll, T[4][4] = 2ll;

    if (N == 1)
        return 1ll;
    T = pow(T, N-1);

    ll res = 0ll;
    REP(i, K)
        res = (res%MOD + (T[3][i]%MOD) * (F1[i]%MOD)) % MOD;
    return res%MOD;

}

int main(){
    ll k,a,b,c,d;
    while(cin>>k && k){
        ll resp[]={32,9,0,8};
        ll arr[]={0,2,2+16,2+16+64,2+16+64+256};
        ll ans = 0;
        if(k <= 4)
          ans = arr[k];
        else
          ans = fib(k-3,resp)+2+16+64+256;
        ans%=MOD;
        cout<<ans<<endl;
    }
    return 0;
}