#include<fstream>
#include<cstring>
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+b,b=e,c+=e,e=aux;
        if(d>1048576) d-=1048576; if(d>1048576) d-=1048576;
        if(c>1048576) c-=1048576;
    }
    fout<<(a+b+c+d+e)%1048576<<"\n";
    return 0;
}