#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include /* PascalCase クラス名 camelCase メソッド名,関数名,変数名 snake_case ファイル名,名前空間,std のメソッド名,変数名,型名に準じる場合 SNAKE_CASE マクロ名,static const 定数,列挙体 */ #define REP(i, n) for (int i = 0; i < (n); i++) #define FOR(i, init, n) for(int i = init; i < (n); i++) #define ALL(obj) (obj).begin(), (obj).end() #define RALL(obj) (obj).rbegin(), (obj).rend() #define Cout(obj) cout << obj << endl #define Size(obj) (int)(obj).size() #define fcout cout << fixed << setprecision(10) #define fi first #define se second using namespace std; using lint = long long int; using vvlint = vector>; using vlint = vector; using vvint = vector>; using vint = vector; const int MOD = 1e9 + 7; const int iINF = 1e9; const long long int llINF = 1e18; const double PI = acos(-1.0); const int dx[4] = {1, 0, -1, 0}; const int dy[4] = {0, 1, 0, -1}; vvlint mul(vvlint &A, vvlint &B) { vvlint C(Size(A), vlint(B[0].size())); REP(i, Size(A)) { REP(j, Size(B)) { REP(k, Size(B[0])) { C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD; } } } return C; } vvlint pow(vvlint A, lint n) { vvlint B(Size(A), vlint(Size(A))); REP(i, Size(A)) { B[i][i] = 1; } while(n > 0) { if(n & 1) B = mul(B, A); A = mul(A, A); n >>= 1; } return B; } int main() { cin.tie(0); ios::sync_with_stdio(false); vvlint A(2, vlint(2)); A[0][0] = A[0][1] = A[1][0] = 1; A[1][1] = 0; lint N; cin >> N; lint n, n_1; A = pow(A, N); n = A[1][0]; A[0][0] = A[0][1] = A[1][0] = 1; A[1][1] = 0; A = pow(A, N + 1); n_1 = A[1][0]; cout << (n * n_1) % MOD << endl; return 0; }