#include #include #include #include #include #define REP(i, a, b) for (int i = int(a); i < int(b); i++) #define dump(val) cerr << __LINE__ << ":\t" << #val << " = " << (val) << endl using namespace std; typedef long long int lli; template vector make_v(size_t a, T b) { return vector(a, b); } template auto make_v(size_t a, Ts... ts) { return vector(a, make_v(ts...)); } const lli mod = 1000000007; class matrix { public: vector> mat; int nsize, msize; matrix(int n, int m) { nsize = n; msize = m; mat.resize(nsize, vector(msize, 0)); } matrix operator+(matrix m) { assert(nsize == m.nsize && msize == m.msize); matrix res(nsize, msize); REP(i, 0, nsize) { REP(j, 0, msize) { res.mat[i][j] = (mat[i][j] + m.mat[i][j]) % mod; } } return res; } matrix operator*(matrix m) { assert(msize == m.nsize); matrix res(nsize, m.msize); REP(i, 0, nsize) { REP(j, 0, m.msize) { REP(k, 0, msize) { res.mat[i][j] = (res.mat[i][j] + (mat[i][k] * m.mat[k][j]) % mod) % mod; } } } return res; } static matrix init(int n) { matrix res(n, n); REP(i, 0, n) { res.mat[i][i] = 1; } return res; } void print() { cout << "---------------------------------" << endl; REP(i, 0, nsize) { REP(j, 0, msize) { cout << mat[i][j] << " "; } cout << endl; } } }; matrix pow(matrix m, lli n) { if (n == 0) return matrix::init(m.nsize); if (n % 2 == 0) { matrix res = pow(m, n / 2); return (res * res); } else { return pow(m, n - 1) * m; } } int main() { lli N; cin >> N; const lli divS = 100000; const lli loop = N / divS; const lli rem = N % divS; matrix l(1, 2), r(2, 1), mid(2, 2), ini = matrix::init(2), fib(2, 2); l.mat[0][0] = r.mat[0][0] = mid.mat[1][1] = fib.mat[0][0] = fib.mat[0][1] = fib.mat[1][0] = 1; matrix res(2, 2), bs(2, 2), ans(2, 2); { matrix a = ini; REP(i, 0, divS) { a = a * fib; bs = bs + a * mid * a; if (i < rem) { res = res + a * mid * a; } } } { matrix a = pow(fib, divS); matrix t = matrix::init(2); REP(i, 0, loop) { ans = ans + t * bs * t; t = t * a; } ans = ans + t * res * t; } ans = l * ans * r; cout << ans.mat[0][0] << endl; return 0; }