1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144

// 42jerrykim.github.io에서 더 많은 정보를 확인 할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;

using int64 = long long;
static const int64 MOD = 1000000007;

static inline int64 modPow(int64 base, int64 exp) {
  int64 result = 1 % MOD;
  base %= MOD;
  while (exp > 0) {
    if (exp & 1) result = (result * base) % MOD;
    base = (base * base) % MOD;
    exp >>= 1;
  }
  return result;
}

// Berlekamp–Massey: 최소 선형 점화계수 rec 반환
// s[n] = sum_{i=1..L} rec[i-1] * s[n-i] (mod MOD)
static vector<int64> berlekamp_massey(const vector<int64>& s) {
  vector<int64> ls, cur; // ls: last successful, cur: current
  int lf = 0;            // last fail index
  int64 ld = 1;          // last delta
  for (int i = 0; i < (int)s.size(); i++) {
    int64 t = 0;
    for (int j = 0; j < (int)cur.size(); j++) {
      t = (t + s[i - j - 1] * cur[j]) % MOD;
    }
    int64 delta = (t - s[i]) % MOD;
    if (delta < 0) delta += MOD;
    if (delta == 0) continue;
    if (cur.empty()) {
      cur.assign(i + 1, 0);
      lf = i;
      ld = delta;
      continue;
    }
    int64 k = delta * modPow(ld, MOD - 2) % MOD;
    vector<int64> c(i - lf - 1, 0);
    c.push_back(k);
    for (auto &x : ls) c.push_back((MOD - x) * k % MOD);
    if ((int)c.size() < (int)cur.size()) c.resize(cur.size(), 0);
    for (int j = 0; j < (int)cur.size(); j++) {
      c[j] = (c[j] + cur[j]) % MOD;
    }
    if (i - lf + (int)ls.size() >= (int)cur.size()) {
      ls = cur;
      lf = i;
      ld = delta;
    }
    cur.swap(c);
  }
  for (auto &x : cur) { x %= MOD; if (x < 0) x += MOD; }
  return cur;
}

// rec(길이 m), 초기 s[0..m-1]로 n번째 항 계산 (O(m^2 log n))
static int64 get_nth(const vector<int64>& rec, const vector<int64>& init, long long n) {
  int m = (int)rec.size();
  if (n < (long long)init.size()) return init[(size_t)n];

  auto combine = [&](const vector<int64>& a, const vector<int64>& b) {
    // 다항식 곱셈 후 rec로 나머지
    vector<int64> res(2 * m + 1, 0);
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < m; j++) {
        res[i + j] = (res[i + j] + a[i] * b[j]) % MOD;
      }
    }
    for (int i = 2 * m - 1; i >= m; --i) {
      for (int j = 1; j <= m; j++) {
        res[i - j] = (res[i - j] + res[i] * rec[j - 1]) % MOD;
      }
    }
    res.resize(m);
    return res;
  };

  vector<int64> pol(m, 0), e(m, 0);
  pol[0] = 1;           // 단위 다항식
  if (m == 1) e[0] = rec[0]; else e[1] = 1; // x

  long long k = n;
  while (k > 0) {
    if (k & 1) pol = combine(pol, e);
    e = combine(e, e);
    k >>= 1;
  }

  int64 ans = 0;
  for (int i = 0; i < m; i++) {
    ans = (ans + pol[i] * init[i]) % MOD;
  }
  return ans;
}

// 초기 항 s가 주어질 때, n번째 항
static int64 guess_nth_term(const vector<int64>& s, long long n) {
  if (n < (long long)s.size()) return s[(size_t)n];
  vector<int64> rec = berlekamp_massey(s);
  if (rec.empty()) return 0;
  return get_nth(rec, s, n);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  // s[n] = 2x2x2x2xn 5D 초콜릿을 1x1x1x1x2 도미노로 채우는 경우의 수 (n=0부터)
  // n=1 -> 272, n=2 -> 589185, n=3 -> 930336768 ...
  const vector<int64> s = {
    1, 272, 589185, 930336768, 853401154, 217676188, 136558333, 415722813, 985269529,
    791527976, 201836136, 382110354, 441223705, 661537677, 641601343, 897033284, 816519670,
    365311407, 300643484, 936803543, 681929467, 462484986, 13900203, 657627114, 96637209,
    577140657, 600647073, 254604056, 102389682, 811580173, 592550067, 587171680, 526467503,
    265885773, 951722780, 219627841, 371508152, 283501391, 159234514, 439380999, 722868959,
    125599834, 351398134, 456317548, 365496182, 614778702, 502680047, 193063685, 309004764,
    743901785, 870955115, 312807829, 160375015, 691844624, 137034372, 350330868, 895680450,
    282610535, 317897557, 28600551, 583305647, 539409363, 327406961, 627805385, 680183978,
    681299085, 954964592, 743524009, 788048339, 699454626, 666369521, 857206425, 490463127,
    477198247, 599963928, 21247982, 107843532, 753662937, 239039324, 608530376, 523383010,
    654448101, 801430395, 393034561, 93313778, 983052766, 240336620, 825539982, 525118275,
    563899476, 706271688, 547405697, 477082486, 664058071, 353207278, 729486413, 795704637,
    999271072, 540749624, 411451016, 736422999, 879369181, 918733916, 982303557, 512499644,
    261033810, 391766409, 334092786, 931794834, 854181848, 821090190, 751839258, 433126935,
    571194155, 52438113, 552977155, 320805296, 173355929, 969659468, 258854248, 159509877,
    374487748, 401382023, 44060530, 510164669, 336596764, 652050424, 373872552, 517226592,
    719871041, 43959496, 235333335, 304962191, 253114421, 43638769, 361871585, 8060121,
    147014624, 114846460, 430864038, 368951246, 863795701, 36066788, 971606149, 935875286,
    486724123, 73790652, 236936530, 307697424, 753314001, 40450345, 529462842, 166162047,
    974102330, 600865526, 63237062, 749041914, 670937123, 806399597, 776678839, 842565920,
    608499253, 469062485, 842196981, 247762946, 778570576, 237951782, 286343384, 988318575,
    147255879, 905747089, 711062313, 21396079, 826846622, 443781794, 786474911, 400737121,
    844768961, 686214818, 590050845, 855473150, 18501778, 33258755, 398169058, 811192244,
    710397887, 591757177, 775311969, 168256434, 509615161, 489764304, 605188191, 498085780,
    164388183, 524662873, 322602324, 853641480, 205349527, 308211944, 93153206
  };

  long long n;
  if (!(cin >> n)) return 0;
  cout << guess_nth_term(s, n) << '\n';
  return 0;
}