#include <stdio.h>
#include <ctype.h>

//      6
// a b 4 5 e f

///      ------[8]------
/// dp[i][0/1][0/1][0/1] =def= numarul de moduri de a face o perm corecta cu primele i nr.
///                            daca primul stegulet e 1 inseamna ca n - 1 e la capat
///                            daca al doilea stegulet e 1 inseamna ca n e la capat
///                            daca al treilea stegulet e 1 inseamna ca n si n - 1 sunt adiacente

/**
**/

#define CEVA_INTRE 0
// n - 1 => 1
// n     => 2
// n + 1 => 3

#define MOD_MASK 1048575

class Matrix {
  public:
    int m[7][7];

    Matrix(){
      int i, j;

      for( i = 0 ; i < 7 ; i++ )
        for( j = 0 ; j < 7 ; j++ )
          m[i][j] = 0;
    }

    void print( FILE *fout ){
      int i, j;

      for( i = 0 ; i < 7 ; i++ ){
        for( j = 0 ; j < 7 ; j++ )
          fprintf( fout, "%d ", m[i][j] );
        fputc( '\n', fout );
      }
    }

} multboi, id;

Matrix operator * ( const Matrix &a, const Matrix &b ){
  int i, j, k;

  Matrix rez;

  for( i = 0 ; i < 7 ; i++ )
    for( j = 0 ; j < 7 ; j++ )
      for( k = 0 ; k < 7 ; k++ )
        rez.m[i][j] += ((((long long)a.m[i][k]) * b.m[k][j]) & MOD_MASK);

  return rez;
}

int mask;
int flags[3];

int compressed[5];
int complen;

int fwdcomp[6];

void calccomp(){
  complen = 0;

  if( !flags[0] )
    compressed[complen++] = CEVA_INTRE;

  compressed[complen++] = 1;// n - 1

  if( !flags[2] )
    compressed[complen++] = CEVA_INTRE;

  compressed[complen++] = 2;// n

  if( !flags[1] )
    compressed[complen++] = CEVA_INTRE;
}

static inline int myabs( int x ){
  return x < 0 ? -x : x;
}

int check_n_print(){
  int i = 0, fwdflag[3], fwdmask;

  for( i = 0 ; i < complen ; i++ )
    if( myabs( fwdcomp[i] - fwdcomp[i + 1] ) > 2 )
      return 0;

  fwdflag[0] = fwdcomp[0] == 2 || fwdcomp[complen] == 2;
  fwdflag[1] = fwdcomp[0] == 3 || fwdcomp[complen] == 3;

  i = 0;
  while( fwdcomp[i] < 2 )
    i++;

  fwdflag[2] = fwdcomp[i + 1] == 2 || fwdcomp[i + 1] == 3;

  //fputc( '0' + fwdflag[0], stdout );
  //fputc( '0' + fwdflag[1], stdout );
  //fputc( '0' + fwdflag[2], stdout );
  //fputc( ' ', stdout );

  fwdmask = (fwdflag[0] << 0) + (fwdflag[1] << 1) + (fwdflag[2] << 2);

  multboi.m[fwdmask - 1][mask - 1]++;

  return 1;
}

void getfwd(){
  int i, pnew, aux;

  fwdcomp[pnew = 0] = 3;
  for( i = 0 ; i < complen ; i++ )
    fwdcomp[i + 1] = compressed[i];

  check_n_print();

  for( i = 0 ; i < complen ; i++ ){
    aux = fwdcomp[i];
    fwdcomp[i] = fwdcomp[i + 1];
    fwdcomp[i + 1] = aux;

    check_n_print();
  }

  //fputc( '\n', stdout );
}

//int defvect[7] = { 0, 0, 0, 0, 0, 0, 2 };

int main(){
  FILE *fin  = fopen( "12perm.in",  "r" );
  FILE *fout = fopen( "12perm.out", "w" );

  int n;
  int i, out;
  Matrix a, rez;

  for( mask = 1 ; mask < 8 ; mask++ ){
    flags[0] = ((mask >> 0) & 1);
    flags[1] = ((mask >> 1) & 1);
    flags[2] = ((mask >> 2) & 1);

    //fputc( '0' + flags[0], stdout );
    //fputc( '0' + flags[1], stdout );
    //fputc( '0' + flags[2], stdout );
    //fputc( ':', stdout );
    //fputc( ' ', stdout );

    calccomp();
    getfwd();
  }

  for( i = 0 ; i < 7 ; i++ )
    id.m[i][i] = 1;

  //multboi.print( stdout );

  fscanf( fin, "%d", &n );

  if( n == 1 ){
    fprintf( fout, "1\n" );
    fclose( fin );
    fclose( fout );
    return 0;
  }

  n -= 2;

  a = multboi;
  rez = id;
  while( n ){
    //fputs( "-----------------------------\n", stdout );
    //rez.print( stdout );
    if( n & 1 )
      rez = rez * a;
    a = a * a;
    n >>= 1;
  }

  //rez.print( stdout );

  out = 0;
  for( i = 0 ; i < 7 ; i++ )
    out += rez.m[i][7 - 1];

  fprintf( fout, "%d\n", (out & MOD_MASK) << 1 );

  fclose( fout );
  fclose( fin );
  return 0;
}