#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);
            for (int i=0;i<n;i++){
                for (int j=0;j<mat2.m;j++){
                    long long 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]={1,0,1,0,1};
            for (int i=0;i<30;i++){
                if (pow&(1<<i)){
                     res=res*x;

                }
                x=x*x;
            }
            return res;
        }
int main()
{
    Gigi>>N;
    Matrice b(5,5);
    b.mat={
        {1,0,1,0,0},
        {0,1,0,1,1},
        {0,1,0,0,0},
        {0,0,1,0,0},
        {0,0,0,0,1}
    };
    Matrice a=expon(b,N-1);
    Marcel<<a.mat[0][0]+a.mat[0][1]+a.mat[0][2]+a.mat[0][3]+a.mat[0][4];
    return 0;
}