#include <bits/stdc++.h>
#define mod 1048576 
using namespace std;
ifstream f("12perm.in");
ofstream g("12perm.out");
int n;

int main()
{
  f>>n;
  if(n == 1)
    g<<1;
  long long p2 = 2, p3 = 6, p4 = 12, aux;
  for(int i = 5;i <= n;++i)
  {
    aux = (p4 + p2 + 2 * (i - 2)) % mod;
    p2 = p3, p3 = p4;
    p4 = aux;
  }
  if(n == 2)
    g<<p2;
  else if(n == 3)
    g<<p3;
  else
    g<<p4;
  return 0;
}