#pragma GCC optimize "Ofast" #include "bits/stdc++.h" // Begin Header {{{ #pragma region using namespace std; using usize = size_t; using imax = intmax_t; using uimax = uintmax_t; #ifndef DEBUG #define dump(...) #endif #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) #define rep(i, b, e) for (intmax_t i = (b), i##_limit = (e); i < i##_limit; ++i) #define repc(i, b, e) for (intmax_t i = (b), i##_limit = (e); i <= i##_limit; ++i) #define repr(i, b, e) for (intmax_t i = (b), i##_limit = (e); i >= i##_limit; --i) #define var(Type, ...) Type __VA_ARGS__; input(__VA_ARGS__) #define let const auto constexpr size_t operator""_zu(unsigned long long value) { return value; }; constexpr intmax_t operator""_jd(unsigned long long value) { return value; }; constexpr uintmax_t operator""_ju(unsigned long long value) { return value; }; constexpr int INF = 0x3f3f3f3f; constexpr intmax_t LINF = 0x3f3f3f3f3f3f3f3f_jd; template > using MaxHeap = priority_queue, Compare>; template > using MinHeap = priority_queue, Compare>; inline void input() {} template inline void input(Head&& head, Tail&&... tail) { cin >> head; input(forward(tail)...); } template ::value, nullptr_t> = nullptr> inline istream& operator>>(istream &is, Container &vs) { for (auto &v: vs) is >> v; return is; } inline void output() { cout << "\n"; } template inline void output(Head&& head, Tail&&... tail) { cout << head; if (sizeof...(tail)) cout << " "; output(forward(tail)...); } template ::value, nullptr_t> = nullptr> inline ostream& operator<<(ostream &os, const Container &vs) { static constexpr const char *delim[] = {" ", ""}; for (auto it = begin(vs); it != end(vs); ++it) { os << delim[it == begin(vs)] << *it; } return os; } template inline void join(const Iterator &Begin, const Iterator &End, const string &delim = "\n", const string &last = "\n") { for (auto it = Begin; it != End; ++it) { cout << ((it == Begin) ? "" : delim) << *it; } cout << last; } template inline vector makeVector(const T &init_value, size_t sz) { return vector(sz, init_value); } template inline auto makeVector(const T &init_value, size_t sz, Args... args) { return vector(init_value, args...))>(sz, makeVector(init_value, args...)); } template class FixPoint : Func { public: explicit constexpr FixPoint(Func&& f) noexcept : Func(forward(f)) {} template constexpr decltype(auto) operator()(Args&&... args) const { return Func::operator()(*this, std::forward(args)...); } }; template static inline constexpr decltype(auto) makeFixPoint(Func&& f) noexcept { return FixPoint{forward(f)}; } template struct reverse_t { Container &c; reverse_t(Container &c) : c(c) {} auto begin() { return c.rbegin(); } auto end() { return c.rend(); } }; template auto reversed(Container &c) { return reverse_t(c); } template inline bool chmax(T &a, const T &b) noexcept { return b > a && (a = b, true); } template inline bool chmin(T &a, const T &b) noexcept { return b < a && (a = b, true); } template inline T diff(const T &a, const T &b) noexcept { return a < b ? b - a : a - b; } void operator|=(vector::reference lhs, const bool rhs) { lhs = lhs | rhs; } void ioinit() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(10); clog << fixed << setprecision(10); } #pragma endregion // }}} End Header // ModInt {{{ template class ModInt { public: using value_type = intmax_t; private: static constexpr value_type cmod = Modulo; // compile-time static value_type rmod; // runtime value_type value = 0; static constexpr value_type inverse(value_type n, value_type m) { value_type a = n; value_type b = m; value_type x = 0; value_type y = 1; for (value_type u = y, v = x; a;) { const value_type t = b / a; swap(x -= t * u, u); swap(y -= t * v, v); swap(b -= t * a, a); } if ((x %= m) < 0) x += m; return x; } static value_type normalize(intmax_t n, value_type m) { if (n >= m) { n %= m; } else if (n < 0) { if ((n %= m) < 0) n += m; } return n; } public: ModInt() = default; ModInt(intmax_t n) : value(normalize(n, getModulo())) {} template constexpr explicit operator T() const { return static_cast(value); } ModInt& operator=(intmax_t n) { value = normalize(n, getModulo()); return *this; } ModInt& operator+=(const ModInt& other) { if ((value += other.value) >= getModulo()) value -= getModulo(); return *this; } ModInt& operator-=(const ModInt& other) { if ((value -= other.value) < 0) value += getModulo(); return *this; } ModInt& operator*=(const ModInt& other) { value = (value * other.value) % getModulo(); return *this; } ModInt& operator/=(const ModInt& other) { value = (value * inverse(other.value, getModulo())) % getModulo(); return *this; } ModInt& operator++() { if (++value == getModulo()) value = 0; return *this; } ModInt& operator--() { if (value-- == 0) value = getModulo() - 1; return *this; } ModInt operator++(int) { const ModInt tmp(*this); ++*this; return tmp; } ModInt operator--(int) { const ModInt tmp(*this); --*this; return tmp; } friend ModInt operator+(ModInt lhs, const ModInt& rhs) { return lhs += rhs; } friend ModInt operator-(ModInt lhs, const ModInt& rhs) { return lhs -= rhs; } friend ModInt operator*(ModInt lhs, const ModInt& rhs) { return lhs *= rhs; } friend ModInt operator/(ModInt lhs, const ModInt& rhs) { return lhs /= rhs; } ModInt operator+() const { return *this; } ModInt operator-() const { if (value == 0) return *this; return ModInt(getModulo() - value); } friend bool operator==(const ModInt& lhs, const ModInt& rhs) { return lhs.value == rhs.value; } friend bool operator!=(const ModInt& lhs, const ModInt& rhs) { return !(lhs == rhs); } friend ostream& operator<<(ostream& os, const ModInt& n) { return os << n.value; } friend istream& operator>>(istream& is, ModInt& n) { is >> n.value; n.value = normalize(n.value, getModulo()); return is; } static value_type getModulo() { return ((cmod > 0) ? cmod : rmod); } template ::type> static T setModulo(value_type m) { rmod = m; } }; template constexpr typename ModInt::value_type ModInt::cmod; template typename ModInt::value_type ModInt::rmod; // }}} // Factorials {{{ template class Factorials { public: using value_type = ModInt; private: mutable vector m_f, m_i, m_fi; public: Factorials() = default; explicit Factorials(intmax_t n) : m_f(n + 1), m_i(n + 1), m_fi(n + 1) { m_f[0] = 1; for (intmax_t i = 1; i <= n; ++i) { m_f[i] = m_f[i - 1] * i; } const intmax_t MOD = m_f[0].getModulo(); m_i[1] = 1; for (intmax_t i = 2; i <= n; ++i) { m_i[i] = -value_type(MOD / i) * m_i[MOD % i]; } m_fi[0] = 1; for (intmax_t i = 1; i <= n; ++i) { m_fi[i] = m_fi[i - 1] * m_i[i]; } } value_type inv(intmax_t n) const { return m_i[n]; } value_type fact(intmax_t n) const { return m_f[n]; } value_type finv(intmax_t n) const { m_fi[n]; } value_type C(intmax_t n, intmax_t k) const { if (k < 0 || n < k) return 0; return m_f[n] * m_fi[k] * m_fi[n - k]; } value_type P(intmax_t n, intmax_t k) const { if (k < 0 || n < k) return 0; return m_f[n] * m_fi[n - k]; } value_type H(intmax_t n, intmax_t k) const { return C(n + k - 1, k); } }; // }}} template T binomial(intmax_t n, intmax_t k) { if (k < 0 || n < k) return 0; T ret = 1; for (intmax_t i = 1; i <= k; ++i) { ret *= n--; ret /= i; } return ret; } template T power(const T& b, const intmax_t& e) { T ret = 1; T n = b; for (intmax_t p = abs(e); p > 0; p >>= 1) { if (p & 1) ret *= n; n *= n; } if (e < 0) return T(1) / ret; return ret; } template T power(const T& b, const string& e) { T ret = 1; for (const char& c: e) { ret = power(ret, 10) * power(b, c - '0'); } return ret; } // Edge {{{ template struct Edge { size_t from, to; Weight weight; Edge() {} Edge(size_t from, size_t to, Weight weight = 1) : from(from), to(to), weight(weight) {} bool operator<(const Edge &rhs) const { return weight < rhs.weight; } bool operator>(const Edge &rhs) const { return weight > rhs.weight; } operator size_t() const { return to; } }; // }}} // Graph {{{ template class Graph : public vector>> { using graph = vector>>; public: Graph() {} Graph(const size_t V) : graph(V) {} void connect(size_t from, size_t to, Weight weight = 1) { (*this)[from].emplace_back(from, to, weight); } friend ostream& operator<<(ostream &strm, const Graph &G) { for (size_t v = 0; v < G.size(); ++v) { strm << '[' << setw(2) << v << ']'; for (const auto &e: G[v]) { strm << ' ' << setw(2) << e.to; } strm << '\n'; } return strm; } }; // }}} // SegmentTree {{{ template struct SegmentTree { const size_t sz; const Func fn; const Monoid unity; vector seg; SegmentTree(const size_t n, const Monoid &u, Func f) : sz(1 << (__lg(n + 5) + 1)), fn(f), unity(u), seg(sz * 2, unity) {} void set(size_t k, const Monoid &v) { seg[k + sz] = v; } Monoid& operator[](size_t k) { return seg[k + sz]; } const Monoid& operator[](size_t k) const { return seg[k + sz]; } void build() { for (size_t k = sz - 1; k > 0; --k) { seg[k] = fn(seg[2 * k], seg[2 * k + 1]); } } void update(size_t k, const Monoid &x) { k += sz; seg[k] = x; while (k >>= 1) { seg[k] = fn(seg[2 * k], seg[2 * k + 1]); } } Monoid fold(size_t l, size_t r) const { Monoid L = unity; Monoid R = unity; for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) { if (l & 1) { L = fn(L, seg[l++]); } if (r & 1) { R = fn(seg[--r], R); } } return fn(L, R); } }; // }}} // BinaryIndexedTree {{{ template struct BinaryIndexedTree { vector bit; const size_t SIZE; explicit BinaryIndexedTree(size_t n) : bit(n + 5, 0), SIZE(1 << (__lg(n + 5) + 1)) {} void add(int i, const T& v) { for (++i; i < bit.size(); i += i & -i) bit[i] += v; } // [0, i] T sum(int i) const { T ret = 0; for (++i; i > 0; i -= i & -i) ret += bit[i]; return ret; } // [s, t] T sum(int s, int t) const { if (s > t) swap(s, t); return sum(t) - sum(s - 1); } size_t lower_bound(T v) const { if (v <= 0) return 0; T x = 0; for (size_t k = SIZE; k > 0; k >>= 1) { if (x + k < bit.size() && bit[x + k] < v) { v -= bit[x + k]; x += k; } } return x; } }; // }}} // dijkstra {{{ template vector dijkstra(const Graph &G, const vector &startNodes) { using P = pair; vector dp(G.size(), numeric_limits::max()); priority_queue, greater<>> pq; for (const auto startNode: startNodes) { dp[startNode] = 0; pq.emplace(0, startNode); } while (!pq.empty()) { const Weight nowCost = pq.top().first; const size_t nowNode = pq.top().second; pq.pop(); if (dp[nowNode] < nowCost) { continue; } for (const auto &e: G[nowNode]) { const Weight newCost = dp[nowNode] + e.weight; const size_t newNode = e.to; if (newCost < dp[newNode]) { dp[newNode] = newCost; pq.emplace(newCost, newNode); } } } return dp; } // }}} // Compress {{{ template class Compress { vector xs; public: Compress() = default; Compress(const vector &vs) { add(vs); } void add(const vector &vs) { copy(vs.begin(), vs.end(), back_inserter(xs)); } void add(const T &x) { xs.emplace_back(x); } void build() { sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end()); } vector get(const vector &vs) const { vector ret; transform(vs.begin(), vs.end(), back_inserter(ret), [&](const T &v) { return distance(xs.begin(), lower_bound(xs.begin(), xs.end(), v)); }); return ret; } unordered_map dict() const { unordered_map ret; for (intmax_t i = 0; i < xs.size(); ++i) { ret[xs[i]] = i; } return ret; } const size_t size() const { return xs.size(); } const T &operator[](size_t k) const { return xs[k]; } }; // }}} const auto sigma = [](auto s, auto t) { return (s + t) * (t - s + 1) / 2; }; // integerOptimizeConvex {{{ template auto integerOptimizeConvex(Tp xl, Tp xu, Fn fn, bool maximize = true) { while (xu - xl > 1) { const Tp xm = (xl + xu) / 2; if (maximize) { if (fn(xm - 1) < fn(xm)) xl = xm; else xu = xm; } else { if (fn(xm - 1) > fn(xm)) xl = xm; else xu = xm; } } return make_pair(xl, fn(xl)); } // }}} vector sieve(size_t MAX) { vector isPrime(MAX + 1, true); isPrime[0] = false; isPrime[1] = false; for (intmax_t i = 2; i * i <= MAX; ++i) { if (isPrime[i]) { for (intmax_t j = 2; i * j <= MAX; ++j) { isPrime[i * j] = false; } } } return isPrime; } // DisjointSet {{{ struct DisjointSet { const size_t n; mutable vector c; explicit DisjointSet(const size_t n) : n(n), c(n, -1) {} size_t size(size_t v) const { return -c[root(v)]; } size_t root(size_t v) const { return (c[v] < 0) ? v : c[v] = root(c[v]); } bool connected(size_t u, size_t v) const { return root(u) == root(v); } bool unite(size_t u, size_t v) { u = root(u); v = root(v); if (u == v) return false; if (-c[u] < -c[v]) swap(u, v); c[u] += c[v]; c[v] = u; return true; } vector> groups() { vector roots(n), group_size(n); for (size_t i = 0; i < n; ++i) { roots[i] = root(i); group_size[roots[i]]++; } vector> res(n); for (size_t i = 0; i < n; ++i) { res[i].reserve(group_size[i]); } for (size_t i = 0; i < n; ++i) { res[roots[i]].emplace_back(i); } res.erase( remove_if(res.begin(), res.end(), [&](const auto& v) { return v.empty(); }), res.end()); return res; } }; // }}} template T extgcd(T a, T b, T &x, T &y) { T g = a; x = 1, y = 0; if (b != 0) { g = extgcd(b, a % b, y, x); y -= (a / b) * x; } return g; } // Matrix {{{ template struct Addition { Tp operator()(const Tp& lhs, const Tp& rhs) { return lhs + rhs; } }; // template // struct Addition { // Tp operator()(const Tp& lhs, const Tp& rhs) { // return lhs | rhs; // } // }; // template // struct Addition { // Tp operator()(const Tp& lhs, const Tp& rhs) { // return lhs ^ rhs; // } // }; template struct Multiplication { Tp operator()(const Tp& lhs, const Tp& rhs) { return lhs * rhs; } }; // template // struct Multiplication { // Change identity!!!! // Tp operator()(const Tp& lhs, const Tp& rhs) { // return lhs & rhs; // } // }; template , typename Mul = Multiplication> class Matrix { private: vector> A; Add add; Mul mul; public: Matrix() = default; Matrix(size_t n, size_t m) : A(n, vector(m, 0)) {} Matrix(size_t n) : A(n, vector(n, 0)) {} Matrix(vector> A) : A(A) {} size_t height() const { return A.size(); } size_t width() const { return A[0].size(); } vector& operator[](size_t k) { return A[k]; } const vector& operator[](size_t k) const { return A[k]; } static Matrix identity(size_t n) { // product Matrix res(n); for (size_t i = 0; i < n; ++i) res[i][i] = 1; return res; } // static Matrix identity(size_t n) { // logical product // Matrix res(n); // for (size_t i = 0; i < n; ++i) res[i][i] = -1; // return res; // } Matrix& operator+=(const Matrix& B) { const size_t n = height(); const size_t m = width(); assert(n == B.height() && m == B.width()); for (size_t i = 0; i < n; ++i) { for (size_t j = 0; j < m; ++j) { A[i][j] += B[i][j]; } } return *this; } Matrix& operator-=(const Matrix& B) { const size_t n = height(); const size_t m = width(); assert(n == B.height() && m == B.width()); for (size_t i = 0; i < n; ++i) { for (size_t j = 0; j < m; ++j) { A[i][j] -= B[i][j]; } } return *this; } Matrix& operator*=(const Matrix& B) { const size_t n = height(); const size_t m = width(); const size_t l = B.width(); assert(m == B.height()); vector> C(n, vector(l, 0)); for (size_t i = 0; i < n; ++i) { for (size_t j = 0; j < m; ++j) { for (size_t k = 0; k < l; ++k) { C[i][k] = add(C[i][k], mul(A[i][j], B[j][k])); } } } A.swap(C); return *this; } Matrix operator+(const Matrix& B) const { return Matrix(A) += B; } Matrix operator-(const Matrix& B) const { return Matrix(A) -= B; } Matrix operator*(const Matrix& B) const { return Matrix(A) *= B; } Matrix pow(intmax_t e) const { Matrix res = identity(height()); Matrix B(A); while (e > 0) { if (e & 1) res *= B; B *= B; e >>= 1; } return res; } Matrix pow(string e) const { Matrix res = identity(height()); Matrix B(A); for (const char c: e) { res = res.pow(10) * B.pow(c - '0'); } return res; } auto& data() { return A; } const auto& data() const { return A; } }; // }}} map primeFactor(intmax_t n) { map ret; for (intmax_t i = 2; i * i <= n; ++i) { while (n % i == 0) { ++ret[i]; n /= i; } } if (n != 1) ret[n] = 1; return ret; } constexpr intmax_t MOD = intmax_t(1e9) + 7; // constexpr intmax_t MOD = 998244353; using Mint = ModInt; Factorials F(1'000'000); const auto inside = [](int y, int x, int H, int W) -> bool { return (y >= 1 && x >= 1 && y <= H && x <= W); }; signed main() { ioinit(); var(imax, N); Matrix A(1, 4); A[0][0] = 1; Matrix B(4, 4); rep(i, 0, 4) rep(j, 0, 4) if (!(i == j)) B[i][j] = 1; A *= B.pow(N); output(A[0][0]); return 0; }