#include <iostream>
#include <fstream>

using namespace std;

int ans = 0,n,t[5];
const int MOD = 1048576;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ifstream cin ("12perm.in");
    ofstream cout ("12perm.out");
    cin >> n;
    if ( n == 1)
        cout <<	1;
    else
        if ( n == 2)
            cout << 2;
        else
            if ( n == 3)
                cout << 6;
            else
                if ( n == 4)
                    cout << 12;
                else
                {
                    t[1] = 12;
                    t[2] = 6;
                    t[3] = 2;
                    for (int i = 5; i <= n; ++i)
                    {
                        ans = (t[1] + t[3] +  2 * ( i - 2)) % MOD;
                        t[3] = t[2];
                        t[2] = t[1];
                        t[1] = ans;
                    }
                    cout << t[1];
                    return 0;
                }
    return 0;
}