#include <fstream>
#include <vector>

using namespace std;

typedef long long ll;

const int MOD = (1 << 20);

class Matrix {
public:
  int l, c;
  vector<vector<int>> mat;
  Matrix() {}
  Matrix(const int _l, const int _c) {
    l = _l, c = _c;
    mat = vector<vector<int>>(l, vector<int>(c, 0));
  }
  Matrix operator*(const Matrix& m) {
    Matrix res(l, m.c);
    for (int i = 0; i < l; ++i)
      for (int j = 0; j < m.c; ++j) {
        ll sum = 0;
        for (int k = 0; k < c; ++k)
          sum += (long long) mat[i][k] * m.mat[k][j];
        res.mat[i][j] = sum % MOD;
      }
    return res;
  }
};

  ifstream cin("12perm.in");
  ofstream cout("12perm.out");
Matrix exp2(Matrix x, int p) {
  Matrix ans(1, 5);
  ans.mat[0] = {1, 0, 1, 0, 1};
  for (int i = 0; i < 30; ++i) {
    if (p & (1 << i))
      ans = ans * x;
    x = x * x;
  }
  return ans;
}

int main() {
  int n;
  cin >> n;
  cin.close();
  Matrix b(5, 5);
  b.mat = {
    {1, 0, 1, 0, 0},
    {0, 1, 0, 1, 1},
    {0, 1, 0, 0, 0},
    {0, 0, 1, 0, 0},
    {0, 0, 0, 0, 1}
  };
  Matrix a = exp2(b, n - 1);
  cout << a.mat[0][0] + a.mat[0][1] + a.mat[0][2] + a.mat[0][3] + a.mat[0][4] << "\n";
  cout.close();
  return 0;
}