#include <stdio.h>

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

typedef long long lint;

lint modulo = (1<<20)-1;

#define mod & modulo

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

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

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

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

  int n, i,j, tmp;

  lint aux[6][6], rez[6][6];

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

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

  FOR(i,1,5)
   FOR(j,1,5)
    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 sol, v[] = {0,1,3,2,6,12};
  
  sol = 0;
  
   FOR(i,1,5)
    sol = (sol + rez[5][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("%d\n", sol);
  
  return 0;
 }