#include<fstream>
#include<cstring>
#define mod 1048576
using namespace std;
ifstream fin("12perm.in");
ofstream fout("12perm.out");
int n,a,b,c,d,e,sol,i,aux;
int main(){
    fin>>n;
    if(n==1||n==2){fout<<n; return 0;}
    a=2;d=2;e=2;
    for(i=4;i<=n;i++)
    {
        aux=d,d=a+d+b,b=e,c=c+e,e=aux;
        if(d>mod) d-=mod; if(d>mod) d-=mod;
        if(c>mod) c-=mod;
    }
    fout<<(a+b+c+d+e)%mod<<"\n";
    return 0;
}