#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define FOR(i,a,b) for (int i=(a);i<(b);i++) #define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--) #define REP(i,n) for (int i=0;i<(n);i++) #define RREP(i,n) for (int i=(n)-1;i>=0;i--) #define VEC2(T, N, M) vector(N, vector(M)); #define inf 0x3f3f3f3f3f3f3f3f #define PB push_back #define MP make_pair #define ALL(a) (a).begin(),(a).end() #define SET(a,c) memset(a,c,sizeof a) #define CLR(a) memset(a,0,sizeof a) #define VS vector #define VI vector #define DEBUG(x) cout<<#x<<": "<b?b:a) #define MAX(a,b) (a>b?a:b) #define pi 2*acos(0.0) #define INFILE() freopen("in0.txt","r",stdin) #define OUTFILE()freopen("out0.txt","w",stdout) #define ll long long #define ull unsigned long long #define pii pair #define pcc pair #define pic pair #define pci pair #define eps 1e-14 #define FST first #define SEC second #define SETUP cin.tie(0), ios::sync_with_stdio(false), cout << setprecision(15) << std::fixed; template using vec2 = std::vector>; namespace { struct input_returnner { ll N; input_returnner(ll N_ = 0) :N(N_) {} template operator vector() const { vector res(N); for (auto &a : res) cin >> a; return std::move(res); } template operator T() const { T res; cin >> res; return res; } template T operator - (T right) { return T(input_returnner()) - right; } template T operator + (T right) { return T(input_returnner()) + right; } template T operator * (T right) { return T(input_returnner()) * right; } template T operator / (T right) { return T(input_returnner()) / right; } template T operator << (T right) { return T(input_returnner()) << right; } template T operator >> (T right) { return T(input_returnner()) >> right; } }; template input_returnner in() { return in(); } input_returnner in() { return input_returnner(); } input_returnner in(ll N) { return std::move(input_returnner(N)); } } template istream& operator >> (istream& is, vector& vec) { for (T& x : vec) is >> x; return is; } template < typename T > struct is_vector : std::false_type {}; template < typename T > struct is_vector> : std::true_type {}; template < typename T > constexpr bool is_vector_v = is_vector::value; template std::ostream& operator<< (std::ostream& out, const std::vector& v) { if (!v.empty()) { for (int i = 0; i < v.size(); ++i) { out << v[i] << (i == v.size() - 1 ? "\n" : (is_vector_v ? "" : ", ")); } } return out; } namespace std { // ref: https://stackoverflow.com/questions/7110301/generic-hash-for-tuples-in-unordered-map-unordered-set template inline void hash_combine(std::size_t& seed, T const& v) { seed ^= std::hash()(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2); } // Recursive template code derived from Matthieu M. template ::value - 1> struct HashValueImpl { static void apply(size_t& seed, Tuple const& tuple) { HashValueImpl::apply(seed, tuple); hash_combine(seed, std::get(tuple)); } }; template struct HashValueImpl { static void apply(size_t& seed, Tuple const& tuple) { hash_combine(seed, std::get<0>(tuple)); } }; template struct hash> { size_t operator()(std::tuple const& tt) const { size_t seed = 0; HashValueImpl >::apply(seed, tt); return seed; } }; template class hash> { public: size_t operator()(const std::pair& x) const { return hash>()(std::tie(x.first, x.second)); } }; } // ref: https://stackoverflow.com/questions/6245735/pretty-print-stdtuple namespace aux { template struct seq {}; template struct gen_seq : gen_seq {}; template struct gen_seq<0, Is...> : seq {}; template void print_tuple(std::basic_ostream& os, Tuple const& t, seq) { using swallow = int[]; (void)swallow { 0, (void(os << (Is == 0 ? "" : ", ") << std::get(t)), 0)... }; } } // aux:: template auto operator<<(std::basic_ostream& os, std::tuple const& t) -> std::basic_ostream& { os << "("; aux::print_tuple(os, t, aux::gen_seq()); return os << ")"; } template std::ostream & operator<<(std::ostream & os, const std::pair & p) { return os << "(" << p.first << ", " << p.second << ")"; } // ref: https://stackoverflow.com/questions/8542591/c11-reverse-range-based-for-loo�Fp template struct reversion_wrapper { T& iterable; }; template auto begin(reversion_wrapper w) { return std::rbegin(w.iterable); } template auto end(reversion_wrapper w) { return std::rend(w.iterable); } template reversion_wrapper REV(T&& iterable) { return { iterable }; } ll MOD = 1e9 + 7; class prime; void solve(); signed main() { SETUP; solve(); #ifdef _DEBUG system("pause"); #endif return 0; } #define int ll // template template struct fkvector { public: vector v; fkvector(size_t size) :v(size) {} size_t size() const { return v.size(); } T& operator [] (const int index) { return v[index]; } T dot(const fkvector& right) { assert(v.size() == right.size()); T res = 0; for (int i = 0; i < right.size(); ++i) { res += v[i] * right.v[i]; } return res; } void operator = (const fkvector& right) { v.clear(); v.resize(right.size()); copy(right.v.begin(), right.v.end(), v.begin()); } fkvector operator + (const fkvector& right) { assert(v.size() == right.size()); fkvector res(v.size()); for (size_t i = 0; i < v.size(); ++i) { res[i] = v[i] + right.v[i]; } return res; } fkvector operator - (const fkvector& right) { assert(v.size() == right.size()); fkvector res(v.size()); for (size_t i = 0; i < v.size(); ++i) { res[i] = v[i] - right.v[i]; } return res; } void operator += (const fkvector& right) { assert(v.size() == right.size()); *this = *this + right; } void operator -= (const fkvector& right) { assert(v.size() == right.size()); *this = *this - right; } void print() { cout << "{"; for (int i = 0; i < v.size()-1; ++i) { cout << v[i] << ", "; } cout << v.back(); cout << "}" << endl; } }; template struct fkmat { vector > mat; size_t getRowCount() const { return mat.size(); } size_t getColomnCount() const { return mat[0].size(); } size_t size() const { return mat.size(); } fkmat(size_t size_row,size_t size_colomn):mat(size_row, vector(size_colomn)) {} vector& operator [] (const int index) { return mat[index]; } //Identity matrix fkmat Identity() { for (int i = 0; i < mat.size(); ++i) { mat[i][i] = 1; } return *this; } void operator = (const fkmat& right) { mat.clear(); mat.resize(right.size()); for (int i = 0; i < right.size(); ++i) { mat[i] = right.mat[i]; } } fkmat operator + (const fkmat& right) { fkmat res(getRowCount(), getColomnCount()); for (int i = 0; i < mat.size(); ++i) { for (int j = 0; j < mat[i].size(); ++j) { res[i][j] = mat[i][j] + right.mat[i][j]; } } return res; } fkmat operator - (const fkmat& right) { fkmat res(getRowCount(), getColomnCount()); for (int i = 0; i < mat.size(); ++i) { for (int j = 0; j < mat[i].size(); ++j) { res[i][j] = mat[i][j] - right.mat[i][j]; } } return res; } fkmat operator * (const fkmat& right) { fkmat res(getRowCount(), getColomnCount()); assert(getColomnCount() == right.getRowCount()); for (int r = 0; r < getRowCount(); ++r) { for (int c = 0; c < right.getColomnCount(); ++c) { for (int k = 0; k < getColomnCount(); ++k) { res[r][c] += mat[r][k] * right.mat[k][c]; res[r][c] %= MOD; } } } return res; } void operator += (const fkmat& right) { for (int i = 0; i < mat.size(); ++i) { for (int j = 0; j < mat[i].size(); ++j) { mat[i][j] += right.mat[i][j]; } } } void operator -= (const fkmat& right) { for (int i = 0; i < mat.size(); ++i) { for (int j = 0; j < mat[i].size(); ++j) { mat[i][j] -= right.mat[i][j]; } } } void operator *= (const fkmat& right) { *this = *this * right; } //power n void pow(long long n, fkmat* dst) { dst->Identity(); fkmat x(getRowCount(), getColomnCount()); x.mat = mat; while (n > 0) { if (n & 1) *dst = *dst * x; x *= x; x %= MOD; n >>= 1; } } //power n void pow(long long n) { fkmat res(getRowCount(), getColomnCount()); res = fkmat(getRowCount(), getColomnCount()).Identity(); fkmat x(getRowCount(), getColomnCount()); x = *this; while (n > 0) { if (n & 1) res = res * x; x *= x; n >>= 1; } *this = res; } void print() { for (size_t i = 0; i < mat.size(); ++i) { for (size_t j = 0; j < mat[i].size(); ++j) { cout << mat[i][j] << " "; } cout << endl; } } }; void solve() { int N; cin >> N; fkmat m(2, 2); for (int i = 0; i < m.size(); ++i) { for (int j = 0; j < m[i].size(); ++j) { m[i][j] = i; } } m[0][0] = 1; m[0][1] = 1; m[1][0] = 1; m[1][1] = 0; m.pow(N); cout << (m[1][0]*m[0][0])%MOD << endl; }