#include <fstream>

using namespace std;

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

const int MOD=(1<<20);

inline int add(int a,int b)
{
    a+=b;
    a|=MOD;
    return a;
}

inline int mul(int a,int b)
{
    return a*(long long)b%MOD;
}

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]=add(a[i-1],a[i-3]);
    }
    int f=0;
    f=add(f,mul(3,a[n]));
    f=add(f,a[n-1]);
    f=add(f,a[n-2]);
    f-=2;
    f-=n;
    f%=MOD,f+=MOD,f%=MOD;
    f=mul(2,f);
    fout<<f<<"\n";
    return 0;
}