#include #define int long long #define pii pair #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) #define ALL(c) (c).begin(),(c).end() #define ZERO(a) memset(a,0,sizeof(a)) #define MINUS(a) memset(a,0xff,sizeof(a)) #define MINF(a) memset(a,0x3f,sizeof(a)) #define POW(n) (1LL<<(n)) #define IN(i,a,b) (a <= i && i <= b) using namespace std; template inline bool CHMIN(T& a,T b) { if(a>b) { a=b; return 1; } return 0; } template inline bool CHMAX(T& a,T b) { if(a inline void SORT(T& a) { sort(ALL(a)); } template inline void REV(T& a) { reverse(ALL(a)); } template inline void UNI(T& a) { sort(ALL(a)); a.erase(unique(ALL(a)),a.end()); } const int MOD = 1000000007; const int INF = 0x3f3f3f3f3f3f3f3f; const double EPS = 1e-10; /* ---------------------------------------------------------------------------------------------------- */ template struct Matrix { vector> A; Matrix() {} Matrix(size_t n, size_t m) : A(n,vector(m,0)) {} Matrix(size_t n) : A(n, vector(n,0)) {} size_t height() const { return (A.size()); } size_t width() const { return (A[0].size()); } inline const vector &operator[](int k) const { return (A.at(k)); } inline vector &operator[](int k) { return (A.at(k)); } static Matrix I(size_t n) { Matrix mat(n); for (int i = 0; i < n; i++) mat[i][i] = 1; return (mat); } Matrix &operator+=(const Matrix &B) { size_t n = height(), m = width(); assert(n == B.height() && m == B.width()); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) ((*this)[i][j] += B[i][j]) %= MOD; return (*this); } Matrix &operator-=(const Matrix &B) { size_t n = height(), m = width(); assert(n == B.height() && m == B.width()); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) ((*this)[i][j] += MOD - B[i][j]) %= MOD; return (*this); } Matrix &operator*=(const Matrix &B) { size_t n = height(), m = B.width(), p = width(); assert(p == B.height()); vector> C(n,vector(m,0)); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) for (int k = 0; k < p; k++) C[i][j] = (C[i][j] + (*this)[i][k] * B[k][j] % MOD) % MOD; A.swap(C); return (*this); } Matrix &operator^=(int k) { Matrix B = Matrix::I(height()); while (k > 0) { if (k & 1) B *= *this; *this *= *this; k >>= 1; } A.swap(B.A); return (*this); } Matrix operator+(const Matrix &B) const { return (Matrix(*this) += B); } Matrix operator-(const Matrix &B) const { return (Matrix(*this) += MOD - B); } Matrix operator*(const Matrix &B) const { return (Matrix(*this) *= B); } Matrix operator^(const int k) const { return (Matrix(*this) ^= k); } friend ostream &operator<<(ostream &os, Matrix &p) { size_t n = p.height(), m = p.width(); for (int i = 0; i < n; i++) { os << "["; for (int j = 0; j < m; j++) { os << p[i][j] << (j + 1 == m ? "]\n" : "."); } } return (os); } }; signed main() { cin.tie(0); ios_base::sync_with_stdio(false); cout << fixed << setprecision(10); int N; cin >> N; Matrix A(2,2),B(2,1); A[0][0] = 1; A[0][1] = 1; A[1][0] = 1; A[1][1] = 0; B[0][0] = 1; B[1][0] = 0; A ^= N; B = A * B; cout << (B[0][0] * B[1][0] % MOD) % MOD << endl; return 0; }