#include <fstream>
#define MOD 1048576
using namespace std;
ifstream f("12perm.in");
ofstream g("12perm.out");
int N;
int DP[10];
void Solve_Dinamic()
{
    int i;
    DP[1]=1;
    DP[2]=2;
    DP[3]=6;
    DP[4]=12;
    for(i=5;i<=N;i++)
    {
        DP[1]=DP[2];
        DP[2]=DP[3];
        DP[3]=DP[4];
        DP[4]=(DP[3]+DP[1]+2*(i-2));
        DP[4]&=MOD;
    }
    if(i>=4)
        g<<DP[4]<<"\n";
    else
        g<<DP[i]<<"\n";
}
int main()
{
    f>>N;
    Solve_Dinamic();
    return 0;
}