#include <fstream>

using namespace std;

ifstream cin("12perm.in");
ofstream cout("12perm.out");

const int M=1048576;
int n;

int main(){
    cin >> n;
    int a = 1, b = 2, c = 6, d = 12;
    
    if (n == 1){
        cout << a << '\n';
        return 0;
    }
    if (n == 2){
        cout << b << '\n';
        return 0;
    }
    if (n == 3){
        cout << c << '\n';
        return 0;
    }
    if (n == 4){
        cout << d << '\n';
        return 0;
    }
    
    for (int i=5; i<=n; ++i){
        int aux = d;
        d = (d + b + 2 * (i - 2)) %M;
        a = b;
        b = c;
        c = aux;
    }
    cout << d << '\n';
}