#include <bits/stdc++.h>
#define mod 1<<20
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 = 3, p4 = 12, aux;
  for(int i = 5;i <= n;++i)
  {
    aux = (p4 + p2 + 2 * (i - 2));
    if(aux >= mod)
      aux -= mod;
    p3 = p4, p2 = p3;
    p4 = aux;
  }
  g<<p4;
  return 0;
}