#include <iostream>
#include <fstream>

#define MODULO 1048576

int rec[15000001];

int calc(int n)
{
  int sols[] = { 0, 1, 2, 6, 12 };
  if (n <= 4) {
    return sols[n];
  }

  // Initialization.
  rec[1] = 1;
  rec[2] = 1;
  rec[3] = 2;
  rec[4] = 4;

  int sum = 8, osum;

  // From 5 onwards, compute.
  for (int i = 5; i <= n; ++i) {
    rec[i] = (rec[i - 1] + rec[i - 3] + 2) & (MODULO - 1);
    osum = sum;
    sum = (sum + rec[i]) % MODULO;
  }

  return (2 * rec[n - 3] + 2 * osum) & (MODULO - 1);
}

int main()
{
  std::ifstream in("12perm.in");
  int n;
  in >> n;
  in.close();

  std::ofstream out("12perm.out");
  out << calc(n) << std::endl;
  out.close();

  return 0;
}