#include <iostream>
#include <fstream>

using namespace std;

int v[15000002];

int main()
{
    ifstream f("12perm.in");
    ofstream g("12perm.out");
    int n;
    f>>n;
    v[1]=1; v[2]=2; v[3]=6; v[4]=12;
    for(int i=5;i<=n;i++)
        v[i]=(v[i-1]+v[i-3]+2*(i-2))%(1<<20);
    g<<v[n]<<'\n';
    f.close();
    g.close();
    return 0;
}