#include<fstream>
#include<vector>
#define MOD 1048576
#define ll long long
std::ifstream fin("12perm.in");
std::ofstream fout("12perm.out");
int A[6]={0, 1, 2, 4, 8}, B[6]={0, 0, 0, 2, 4};
int n;
class mat{
public:
    std::vector<std::vector<ll>>a{6, std::vector<ll>(6)};
    mat(const std::vector<std::vector<int>>&source)
    {
        for(int i=0; i<5; ++i)
            for(int j=0; j<5; ++j)
                a[i][j]=source[i][j];
    }
    mat()
    {
        for(int i=0; i<5; ++i)
            a[i][i]=1;
    }
    mat(int x)
    {
        for(int i=0; i<5; ++i)
            for(int j=0; j<5; ++j)
                a[i][j]= x;
    }
    void operator*=(const mat &other)
    {
        mat local(0);
        for(int i=0; i<5; ++i)
            for(int j=0; j<5; ++j)
                for(int k=0; k<5; ++k)
                    local.a[i][j]=(local.a[i][j]+this->a[i][k]*(other.a[k][j]))%MOD;

        for(int i=0; i<5; ++i)
            for(int j=0; j<5; ++j)
                this->a[i][j]=local.a[i][j];
    }
    void operator=(const mat &other)
    {
        for(int i=0; i<5; ++i)
            for(int j=0; j<5; ++j)
                this->a[i][j]=other.a[i][j];
    }
};
inline mat lgexp(mat &base, int exp)
{
    mat p;
    while(exp)
    {
        if(exp&1)
        {
            p*=base;
        }
        base*=base;
        exp>>=1;
    }
    return p;
}
inline void solve()
{
    if(n<=4)
        fout<<A[n]+B[n];
    else
    {
        mat aux({{1, 0, 1, 0, 1},
                        {1, 0, 0, 0, 0},
                        {0, 1, 0, 0, 0},
                        {0, 1, 0, 1, 0},
                        {0, 0, 0, 0, 1}
        });
        aux=lgexp(aux, n-4);
        ll aa=aux.a[0][0]*A[4]+aux.a[0][1]*A[3]+aux.a[0][2]*A[2]+aux.a[0][3]*B[4]+aux.a[0][4]*2;
        aa%=MOD;
        ll bb=aux.a[3][0]*A[4]+aux.a[3][1]*A[3]+aux.a[3][2]*A[2]+aux.a[3][3]*B[4]+aux.a[3][4]*2;
        bb%=MOD;
        ll ans=(aa+bb)%MOD;
        fout<<ans;
    }
}
int main()
{
    fin>>n;
    solve();
    return 0;
}