//================================= // Created on: 2018/07/28 00:18:13 //================================= #include #define show(x) std::cerr << #x << " = " << x << std::endl using ll = long long; constexpr ll MOD = 1000000007LL; using V = std::array; using M = std::array; M mul(const M& m1, const M& m2) { M ans{{{0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}}}; for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { for (int k = 0; k < 4; k++) { (ans[i][j] += m1[i][k] * m2[k][j]) %= MOD; } } } return ans; } M pow(const M& m, const ll n) { if (n == 0) { return M{{{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}}}; } if (n % 2 == 1) { return mul(pow(m, n - 1), m); } else { const auto pp = pow(m, n / 2); return mul(pp, pp); } } int main() { ll N; std::cin >> N; M m{{{1, 1, 0, 0}, {1, 0, 0, 0}, {1, 0, 1, 0}, {0, 1, 0, 1}}}; m = pow(m, N + 1); std::cout << m[2][1] << std::endl; return 0; }