#include <stdio.h>

#define FOR(iii,aa,bb) for( iii = (aa) ; iii <= (bb) ; ++iii )

typedef int lint;

lint modulo = (1<<20);

#define mod % modulo

void mul(lint A[7][7],lint B[7][7])
 {
  lint i,j,k;
  lint rez[7][7];

  FOR(i,1,6)
   FOR(j,1,6)
    rez[i][j] = 0;

  FOR(i,1,6)
   FOR(j,1,6)
    FOR(k,1,6)
     rez[i][j] = (rez[i][j] mod) + ( (A[i][k] mod) * (B[k][j] mod)  )mod ;
     
  FOR(i,1,6)
   FOR(j,1,6)
    B[i][j] = rez[i][j];
 }

int main()
 {
  freopen("12perm.in","r",stdin);
  freopen("12perm.out","w",stdout);

  lint n, i,j, sol, tmp;

  lint aux[7][7], rez[7][7];

  scanf("%lld", &n);
  
  
  tmp = n; 

  aux[1][1] = 1;aux[1][2] = 0;aux[1][3] = 0;aux[1][4] = 0;aux[1][5] = 0;aux[1][6] = 0;
  aux[2][1] = 1;aux[2][2] = 1;aux[2][3] = 0;aux[2][4] = 0;aux[2][5] = 0;aux[2][6] = 0;
  aux[3][1] = 0;aux[3][2] = 0;aux[3][3] = 0;aux[3][4] = 1;aux[3][5] = 0;aux[3][6] = 0;
  aux[4][1] = 0;aux[4][2] = 0;aux[4][3] = 0;aux[4][4] = 0;aux[4][5] = 1;aux[4][6] = 0;
  aux[5][1] = 0;aux[5][2] = 0;aux[5][3] = 0;aux[5][4] = 0;aux[5][5] = 0;aux[5][6] = 1;
  aux[6][1] = 0;aux[6][2] = 2;aux[6][3] = 0;aux[6][4] = 1;aux[6][5] = 0;aux[6][6] = 1;
    

  FOR(i,1,6)
   FOR(j,1,6)
    rez[i][j] = (i == j);

  n-=4;

  while(n>0)
   {
    if(n % 2 == 1)
     mul(aux,rez);

    n /= 2;

    if(n)
     mul(aux,aux);
   }

  int v[] = {0,1,3,1,2,6,12};
  
  sol = 0;
   FOR(i,1,6)
    sol = (sol + rez[6][i]*v[i]mod)mod;
  
  if(tmp < 5) 
   {
    if(tmp  == 1)
     sol = 1;
      else
    if(tmp == 2)  
     sol = 2;
      else
    if(tmp == 3) 
     sol = 6;
      else
     sol = 12;  
   }

  printf("%lld\n", sol);
  
  return 0;
 }