#include <bits/stdc++.h>
using namespace std;

#define all(x) begin(x), end(x)
#ifdef CKISEKI
#define safe cerr << __PRETTY_FUNCTION__ << " line " << __LINE__ << " safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
#include <experimental/iterator>
void debug_(auto s, auto ...a) {
  cerr << "\e[1;32m(" << s << ") = (";
  int f = 0;
  (..., (cerr << (f++ ? ", " : "") << a));
  cerr << ")\e[0m\n";
}
void orange_(auto s, auto L, auto R) {
  cerr << "\e[1;33m[ " << s << " ] = [ ";
  using namespace experimental;
  copy(L, R, make_ostream_joiner(cerr, ", "));
  cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

using lld = int64_t;

constexpr int mod = 1'000'000'007;

int add(int a, int b) {
  assert(0 <= a and a < mod);
  assert(0 <= b and b < mod);
  return a + b >= mod ? a + b - mod : a + b;
}
int mul(lld a, lld b) {
  assert(0 <= a and a < mod);
  assert(0 <= b and b < mod);
  return static_cast<int>(a * b % mod);
}

using Mat = array<array<int, 4>, 4>;
Mat mul(const Mat &a, const Mat &b) {
  Mat c = {};
  for (int i = 0; i < 4; i++)
    for (int k = 0; k < 4; k++)
      for (int j = 0; j < 4; j++)
        c[i][j] = add(c[i][j], mul(a[i][k], b[k][j]));
  return c;
}
consteval Mat Idx() {
  Mat ret;
  for (int i = 0; i < 4; ++i)
    for (int j = 0; j < 4; ++j)
      ret[i][j] = i == j;
  return ret;
}

Mat ksm(Mat a, int k) {
  Mat r = Idx();
  while (k) {
    if (k & 1)
      r = mul(r, a);
    k >>= 1;
    a = mul(a, a);
  }
  return r;
}


int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int n;
  while (cin >> n) {
    if (n == 1) {
      cout << "1\n";
    } else if (n == 2) {
      cout << "2\n";
    } else if (n == 3) {
      cout << "6\n";
    } else if (n == 4) {
      cout << "16\n";
    } else if (n == 5) {
      cout << "36\n";
    } else if (n == 6) {
      cout << "80\n";
    } else {
      Mat a = {};
      a[0][0] = 2, a[0][2] = 1, a[0][3] = 1;
      a[1][0] = 1;
      a[2][1] = 1;
      a[3][3] = 1;

      auto b = ksm(a, n - 5);
      int ans = add(add(mul(b[0][0], 36), mul(b[0][1], 16)), add(mul(b[0][2], 6), mul(b[0][3], 2)));
      cout << ans << '\n';
    }
  }
  return 0;
}