#include #include using namespace std; using namespace atcoder; using ll = long long; using mint = modint1000000007; template struct Matrix : vector> { using vector>::vector; using vector>::operator=; Matrix() {} Matrix(ll N) { *this = vector>(N, vector(N, T())); for(ll i = 0; i < N; i++) { (*this)[i][i] = 1; } } Matrix(ll H, ll W, T x = 0) { *this = vector>(H, vector(W, x)); } Matrix(vector> v) { *this = v; } Matrix operator+(const Matrix &m) const { return Matrix(*this) += m; } Matrix operator-(const Matrix &m) const { return Matrix(*this) -= m; } Matrix operator*(const Matrix &m) const { return Matrix(*this) *= m; } Matrix operator*(const T &x) const { return Matrix(*this) *= x; } Matrix operator^(ll n) const { return Matrix(*this) ^= n; } Matrix operator+=(const Matrix &m) const { ll h = this->size(), w = (*this)[0].size(); assert(h == m.size() && w == m[0].size()); for(ll i = 0; i < h; i++) { for(ll j = 0; j < w; j++) { *this[i][j] += m[i][j]; } } return *this; } Matrix operator-=(const Matrix &m) { ll h = this->size(), w = (*this)[0].size(); assert(h == m.size() && w == m[0].size()); for(ll i = 0; i < h; i++) { for(ll j = 0; j < w; j++) { *this[i][j] -= m[i][j]; } } return *this; } Matrix operator*=(const Matrix &m) { ll h = this->size(), w = (*this)[0].size(); assert(w == (ll)m.size()); vector> r(h, vector(m[0].size(), T(0))); for(ll i = 0; i < h; i++) { for(ll j = 0; j < (ll)m[0].size(); j++) { for(ll k = 0; k < w; k++) { r[i][j] += (*this)[i][k] * m[k][j]; } } } this->swap(r); return *this; } Matrix operator*=(const T &x) { ll h = this->size(), w = (*this)[0].size(); for(ll i = 0; i < h; i++) { for(ll j = 0; j < w; j++) { *this[i][j] *= x; } } return *this; } Matrix operator^=(ll n) { ll h = this->size(); Matrix m(h); while(n) { if(n & 1) { m *= *this; } *this *= *this; n >>= 1LL; } this->swap(m); return *this; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll N; cin >> N; Matrix A = {{0, 1, 0, 1}, {1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}}; Matrix B = {{1, 1, 1, 1}, {1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}}; Matrix dp = {{3}, {1}, {1}, {1}}; if(N == 1) { cout << 1 << "\n"; } if(N == 2) { cout << 1 << "\n"; } if(N == 3) { cout << 3 << "\n"; } if(N < 4) { return 0; } auto C = B * A; dp = (C ^ ((N - 3) / 2)) * dp; if(~N & 1) { dp = A * dp; } cout << dp[0][0].val() << "\n"; }