#include <bits/stdc++.h>
#define MOD 1048576
using namespace std;
ifstream fin("12perm.in");
ofstream fout("12perm.out");

int main(){
  int n, x, x_ = 12, x__ = 6, x___ = 2;
  fin >> n;
  if (n == 1)
    x = 1;
  else if (n < 5)
    x = n * (n - 1);
  else
    for (int i = 5; i <= n; i++){
      x = (x_ + x___ + 2 * i - 4) % MOD;
      x___ = x__ % MOD;
      x__ = x_ % MOD;
      x_ = x % MOD;
    }
  fout << x << "\n";
  return 0;
}