#include <fstream>

using namespace std;

ifstream fin("12perm.in");
ofstream fout("12perm.out");

const int MOD=(1<<20);



const int N=15000000+1;
int a[N];

int main()
{
    int n;
    fin>>n;
    a[0]=a[1]=a[2]=1;
    for(int i=3;i<=n;i++)
    {
        a[i]=a[i-1];
        a[i]+=a[i-3];
        if(a[i]>=MOD)
            a[i]-=MOD;
    }
    int f=0;
    f+=3*a[n]; f%=MOD;
    f+=a[n-1]+a[n-2]; f%=MOD;
    f-=2;
    f-=n;
    f%=MOD,f+=MOD,f%=MOD;
    f+=f;
    f%=MOD;
    fout<<f<<"\n";
    return 0;
}