#include <cstdio>
#define MOD 1048576

long n;

int T[15000003];

int main()
{
  freopen("12perm.in","r",stdin);
  freopen("12perm.out","w",stdout);
  scanf("%ld\n",&n);
  
  T[1] = 1;
  T[2] = 2;
  T[3] = 6;
  T[4] = 12;
  
  for(int i=5; i<=n; i++)
    T[i] = (T[i - 1] + T[i - 3] + 2 * (i - 2) ) % MOD;
    
  printf("%d\n",T[n]);
  return 0;
}