#include <bits/stdc++.h>
#define mod 1048576

std::ifstream fin ("12perm.in");
std::ofstream fout ("12perm.out");

int main(){
    int n, i;
    fin >> n;
    int x[4] = {12, 1, 2, 6};
    int p4, p3=12, p2=6, p1=2;
    if (n == 1)
        fout << 1;
    else if (n == 2)
        fout << 2;
    else if (n == 3)
        fout << 6;
    else if (n == 4)
        fout << 12;
    else{
        for (i=5; i<=n; i++){
            p4 = p3 + p1 + 2*(i-2);
            while (p4 > mod)
                p4 -= mod;
            p1 = p2;
            p2 = p3;
            p3 = p4;
        }
        fout << p3;
    }
    return 0;
}