#include <bits/stdc++.h>

using ll = long long;

const int MOD = 1048576;

int main() {
  std::ifstream fin("12perm.in");
  std::ofstream fout("12perm.out");
  int n;
  fin >> n;
  if (n == 1) {
    fout << "1";
  } else if (n == 2) {
    fout << "2";
  } else if (n == 3) {
    fout << "6";
  } else if (n == 4) {
    fout << "12";
  } else {
    int a1 = 2;
    int a2 = 6;
    int a3 = 12;
    int answer = 0;
    for (int i = 5; i <= n; i++) {
      answer = (a3 + a1 + 2 * (i - 2)) % MOD;
      a1 = a2;
      a2 = a3;
      a3 = answer;
    }
    fout << answer;
  }
  return 0;
}