#include <iostream>
#include <fstream>

using namespace std;

ifstream f("12perm.in");
ofstream g("12perm.out");

int dp[5],n;
int mod=1048576;

int main()
{
    f >> n;
    if(n <= 2)
    {
        g << n;
        return 0;
    }
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 6;
    dp[0] = 12;
    for(int i=5; i<=n; i++)
    {
        dp[i%4] = (dp[(i-1)%4] + dp[(i-3)%4] + 2*(i-2));
        while (dp[i%4] > mod)
            dp[i%4] -= mod;
    }
    g << dp[n%4];
    return 0;
}