#include <cstdint>
#include <cstddef>
#include <iostream>
#include <fstream>
#include <limits>

// ⚛ Rezolvare:
// ▮ 5, 3, 1⃞, 2, 4, ▮ 6⃞ , ...
// ▮ 4, 2, 1⃞, 3, ▮ 5⃞ , ...
// 
// Explicație:
// După ce fixăm valoarea 1 pe o poziție, o parte din valori sunt determinate,
// iar cele nedeterminate pot fi puse în corespondență cu o sub-problemă.
// 
// ▮ 1⃞, 2⃞, ...                → "+c[n-1]"
// ▮ 1⃞, 3, 2, 4⃞, ...          → "+c[n-3]"
// ▮ 1, 3, 5, 7, 8, 6, 4, 2   → "+1" (n par)
// ▮ 1, 3, 5, 7, 6, 4, 2      → "+1" (n impar)
// c[n] = c[n-1] + c[n-3] + 1.
// 
// Explicație:
// 
// Atunci cînd numărăm cele c[n] secvențe cu valoarea 1 pe poziția 1,
// valoarea 2 este
//    • pe poziția 1, în c[n-1] subsecvențe,
//    • pe poziția 3, în c[n-2] subsecvențe,
//    • pe poziția n, într-o singură subsecvență.

// ____________________________________________________________________________

namespace
{

// Spațiul de nume, anonim începe aici ...


bool
demo
()
{ bool  ok;
  
  ::std::ifstream  is("12perm.in");
  
  ::std::uint_least32_t  n;
  is >> n;
  ok = is.good();
  if( !ok)
  { ::std::cerr << "Citire eșuată." << ::std::endl;
    return false; // Eșec.
  }
  
  ::std::uint_least32_t  const min_n = 1;
  ::std::uint_least32_t  const max_n = 15000000;
  
  ok = ( (min_n <= n) && (max_n >= n)  );
  if( !ok)
  { ::std::cerr << "Intrare invalidă: n." << ::std::endl;
    return false; // Eșec.
  }
  
  ::std::uint_least32_t  max_v = 
    ::std::numeric_limits < ::std::uint_least32_t > :: max();
  ok = (max_n < max_v);
  if( !ok)
  { ::std::cerr << "Implementare incorectă." << ::std::endl;
    return false; // Eșec.
  }
  
  // Este adevărat că  (x % 2ⁿ) == (x & (2ⁿ-1)  ).
  // Și-ul pe biți este mai rapid decît aflarea restului după împărțire.
  ::std::uint_least32_t  const mask  = ((1<<20)-1);
  
  // c[n] ― numărul permutărilor π ∈ Sₙ, cu următoarele două proprietăți:
  //        • ∀ i ∈ ℤ  ( (2≤i) ∧ (i≤n)  ) ⇒ ( {1, 2} ∈ |π(i) - π(i-1)|  )
  //        • π(1) = 1.
  
  // x[n] ― numărul permutărilor π ∈ Sₙ, cu proprietatea:
  //        • ∀ i ∈ ℤ  ( (2≤i) ∧ (i≤n)  ) ⇒ ( {1, 2} ∈ |π(i) - π(i-1)|  )
  
  
  // Ne propunem să menținem următorul invariant:
  //   • u[t] == c[i+t], t←0..4.
  ::std::uint_least32_t  i = 1;
  ::std::uint_least32_t  u[3] = {1, 1, 2};
  auto  getC =
    [&i, &u]
    ( ::std::uint_least32_t  const m
    )
    { ::std::uint_least32_t  r;
      while(i<m)
      { r = (1 + (u[3-1] + u[3-3])  );
        u[0] = u[1];
        u[1] = u[2];
        u[2] = (r & mask);
        ++i;
      }
      return u[0];
    }
    ;
  // Calculăm numărul x[n], în variabila s.
  ::std::uint_least32_t  s = 0;
  if(0 != (n%2)  )
  { // Numărăm cele două secvențe în care 1 este în mijloc.
    // De exemplu,
    //    n: 5  (n > 1)
    //   π₁: 4 2 1⃞ 3 5
    //   π₂: 5 3 1⃞ 2 4
    // , sau
    //    n: 1
    //    π: 1
    if(1<n)
    { s = (mask & (s + 2)  );
    }
    else
    { s = (mask & (s + 1)  );
    }
  }
  
  ::std::uint_least32_t  k;
  ::std::uint_least32_t  h;
  ::std::uint_least32_t  e;
  ::std::uint_least32_t  d;
  ::std::size_t  f;
  
  // 4: 0 1⃞ 2 3
  // 5: 0 1 2 3 4
  k = n/2;
  while(0<k)
  { --k;
    // Numărăm secvențele în care 1 este pe poziția k, k ≤ ⌊n/2⌋.
    // 
    // Exemplu:
    // k: 0
    // ▮ 1⃞ ... 
    // k: 3
    // ▮ 6 4 2 1⃞ 3 5 ▮ 7⃞ ...    → c[n-2k].
    // ▮ 7 5 3 1⃞ 2 4 6 ▮ 8⃞ ...  → c[n-(2k+1)]
    
    if(0==k)
    { e = getC(n);
    }
    else
    { e = 0;
      f = 2;
      h = (1+(2*k));
      while(0<f)
      { --f;
        d = (n<=h) ? 1 : getC(n-h);
        e = (e+d) & mask;
        --h;
      }
    }
    
    s = (s + e) & mask;
    
    // Apoi, există tot atâtea secvențe în care 1 este pe poziția n-k.
    s = (s + e) & mask;
  }
  
  // no-throw, no-fail
  ::std::ofstream  os("12perm.out");
  os << s << ::std::endl;
  
  ok = os.good();
  if( !ok)
  { ::std::cerr << "Scriere eșuată." << ::std::endl;
    return false; // Eșec.
  }
  
  return true; // Izbândă.
}

// ____________________________________________________________________________

}

// ... spațiu de nume, anonim se sfârși.

int
main
()
{ int  status;
  
  try
  { bool  const ok = demo();
    status = ( ok ? 0 : 1 );
  }
  catch ( ... )
  { status = 2;
  }
  
  return status;
}


// ____________________________________________________________________________