#include <fstream>
#include <vector>
using namespace std;
ifstream Gigi ("12perm.in");
ofstream Marcel ("12perm.out");
const int mod=1048576;
long long N;

class Matrice{
    public:
        int n,m;
        vector <vector <long long>> mat;
        Matrice (){}
        Matrice (int,int);
        Matrice operator*(const Matrice& mat2){
            Matrice resultat (n,mat2.m);
            long long suma=0;
            for (int i=0;i<n;i++){
                for (int j=0;j<mat2.m;j++){
                    suma=0;
                    for (int k=0;k<m;k++){
                        suma+=(long long)mat[i][k]*mat2.mat[k][j];


                    }
                    resultat.mat[i][j]=suma%mod;
                }
            }
            return resultat;
        }

};
Matrice::Matrice(int n1,int m1)
{
    n=n1;
    m=m1;
    mat=vector <vector <long long>> (n,vector<long long>(m,0));
}
Matrice expon(Matrice x, long long pow)
        {
            Matrice res(1,5);
            res.mat[0]={0,2,2,0,2};
            for (long long i=0;i<33;i++){
                if (pow&(1LL<<i)){
                     res=res*x;
                    ///Marcel<<res.mat[0][0]<<" "<<res.mat[0][1]<<" "<<res.mat[0][2]<<" "<<res.mat[0][3]<<" "<<res.mat[0][4]<<"\n";
                }
                x=x*x;
            }
            return res;
        }
int main()
{
    Gigi>>N;
    if (N==1){
        Marcel<<1;
        return 0;
    }
    if (N==2){
        Marcel<<2;
        return 0;
    }
    Matrice b(5,5);
    b.mat={
        {1,0,0,0,0},
        {0,1,1,0,0},
        {1,0,0,1,0},
        {0,1,0,0,0},
        {0,1,0,0,1}
    };
    Matrice a=expon(b,N-3);
    Marcel<<(a.mat[0][0]+a.mat[0][1]+a.mat[0][2]+a.mat[0][3]+a.mat[0][4])%mod;
    return 0;
}