#include <fstream>
#define modulo 1048576

using namespace std;

int main()
{
    int n, i, t1, t2, t3, t4, t;
    ifstream fin("12perm.in");
    ofstream fout("12perm.out");
    fin >> n;
    fin.close();

    t1 = 1, t2 = 2, t3 = 6, t4 = 12;
    i = 0;
    if (n == 1) i = 1;
    else if (n == 2) i = 2;
    else if (n == 3) i = 6;
    else if (n == 4) i = 12;
    if (i != 0)
    {
        fout << i << "\n";
        fout.close();
        return 0;
    }
    for (i = 5; i <= n; ++i)
    {
        t = (t4 + t2 + 2 * (i - 2)) % modulo;
        t1 = t2; t2 = t3; t3 = t4; t4 = t;
    }
    fout << t4 << "\n";
    fout.close();
    return 0;
}