#include <iostream>
#include <fstream>

#define MODULO 1048576

int rec[15000001];
int sol[15000001];
int sum[15000001];

int calc(int n)
{
  // Initialization.
  rec[1] = 1;
  sum[1] = 1;
  sol[1] = 1;

  rec[2] = 1;
  sum[2] = 2;
  sol[2] = 2;

  rec[3] = 2;
  sum[3] = 4;
  sol[3] = 6;

  rec[4] = 4;
  sum[4] = 8;
  sol[4] = 12;

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

  return sol[n];
}

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;
}