#include #include #include #include #include #include using namespace std; constexpr int mod = 1e9 + 7; struct modint { int n; modint(int n = 0) : n(n) {} }; modint operator+(modint a, modint b) { return modint((a.n += b.n) >= mod ? a.n - mod : a.n); } modint operator-(modint a, modint b) { return modint((a.n -= b.n) < 0 ? a.n + mod : a.n); } modint operator*(modint a, modint b) { return modint(1LL * a.n * b.n % mod); } bool operator<(modint a, modint b) { return a.n < b.n; } modint &operator+=(modint &a, modint b) { return a = a + b; } modint &operator-=(modint &a, modint b) { return a = a - b; } modint &operator*=(modint &a, modint b) { return a = a * b; } modint modinv(modint n) { if (n.n == 1) return 1; return modinv(mod % n.n) * (mod - mod / n.n); } modint operator/(modint a, modint b) { return a * modinv(b); } modint simpath(int n) { constexpr int H = 4; vector> es; for (int x = 0; x < n; x++) { for (int y = 0; y < H; y++) { if (y + 1 < H) es.emplace_back(x * H + y, x * H + y + 1); if (x + 1 < n) es.emplace_back(x * H + y, x * H + y + H); } } vector deg(n * H); for (auto e : es) { deg[e.first]++; deg[e.second]++; } map, modint> dp0, dp1; dp0[{{0, 0}}] = 1; for (auto e : es) { const int u = e.first; const int v = e.second; deg[u]--; deg[v]--; dp1.clear(); for (auto kv : dp0) { map mate1 = kv.first; if (!kv.first.count(v)) mate1[v] = v; const int mu = mate1[u]; const int mv = mate1[v]; const bool del = deg[u] == 0 && u != 0; if (del) mate1.erase(u); if (!del || mu == u || mu == -1) dp1[mate1] += kv.second; if (mu == v || mu == -1 || mv == -1) continue; mate1[u] = -1; mate1[v] = -1; mate1[mu] = mv; mate1[mv] = mu; if (del) mate1.erase(u); if (!del || mu != u) dp1[mate1] += kv.second; } swap(dp0, dp1); } for (auto kv : dp0) { auto mate = kv.first; if (mate[H * n - 1] == 0) return kv.second; } return -1; } // ref: https://en.wikipedia.org/wiki/Berlekamp%E2%80%93Massey_algorithm vector berlekamp_massey(vector s) { const int N = s.size(); vector C(N); vector B(N); C[0] = 1; B[0] = 1; int L = 0; int m = 1; modint b = 1; for (int n = 0; n < N; n++) { modint d = s[n]; for (int i = 1; i <= L; i++) d += C[i] * s[n - i]; if (d.n == 0) { m++; } else if (2 * L <= n) { auto T = C; for (int i = 0; i + m < N; i++) C[i + m] -= B[i] * (d / b); L = n + 1 - L; B = T; b = d; m = 1; } else { for (int i = 0; i + m < N; i++) C[i + m] -= B[i] * (d / b); m++; } } C.resize(L + 1); reverse(C.begin(), C.end()); return C; } vector poly_mod(vector a, const vector &m) { const int n = m.size(); for (int i = a.size() - 1; i >= m.size(); i--) { for (int j = 0; j < m.size(); j++) { a[i - n + j] += a[i] * m[j]; } } a.resize(m.size()); return a; } // a*b mod m vector poly_mul(const vector &a, const vector &b, const vector &m) { vector ret(a.size() + b.size() - 1); for (int i = 0; i < a.size(); i++) { for (int j = 0; j < b.size(); j++) { ret[i + j] += a[i] * b[j]; } } return poly_mod(ret, m); } // x^n mod m vector nth_power(long long n, const vector &m) { vector ret(1); vector x(2); ret[0] = x[1] = 1; while (n > 0) { if (n & 1) ret = poly_mul(ret, x, m); x = poly_mul(x, x, m); n /= 2; } return poly_mod(ret, m); } int main() { vector a(30); for (int i = 0; i < a.size(); i++) { a[i] = simpath(i + 1); } vector m = berlekamp_massey(a); m.pop_back(); for (int i = 0; i < m.size(); i++) { m[i] *= mod - 1; } long long n; cin >> n; auto x = nth_power(n, m); modint ans; for (int i = 0; i < x.size(); i++) { ans += x[i] * a[i]; } cout << ans.n << endl; }