#include using namespace std; #define REP(i,m,n) for(int i=(m); i<(int)(n); i++) #define RREP(i,m,n) for(int i=(int)(n-1); i>=m; i--) #define rep(i,n) REP(i,0,n) #define rrep(i,n) RREP(i,0,n) #define all(a) (a).begin(),(a).end() #define rall(a) (a).rbegin(),(a).rend() #define fi first #define se second #define debug(...) {cerr<<"[L"<<__LINE__<<"] "; _debug(__VA_ARGS__);} template string join(const vector&v, string del=", "){ stringstream s; for(auto x : v) s << del << x; return s.str().substr(del.size()); } template ostream& operator<<(ostream& o, const vector&v){ if(v.size()) o << "[" << join(v) << "]"; return o; } template ostream& operator<<(ostream& o, const vector >&vv){ int l = vv.size(); if(l){ o< void _debug(const First& first, const Rest&... rest){cerr< pii; typedef pair pll; typedef vector vi; typedef vector vvi; typedef vector vl; typedef vector vvl; const double PI = (1*acos(0.0)); const double EPS = 1e-9; const int INF = 0x3f3f3f3f; const ll INFL = 0x3f3f3f3f3f3f3f3fLL; const ll mod = 1e9 + 7; inline void finput(string filename) { freopen(filename.c_str(), "r", stdin); } struct mint { long long x; mint(long long x=0) : x((x%mod+mod)%mod) {} mint operator-() const { return mint(-x); } mint& operator+=(const mint& a) { if ((x += a.x) >= mod) x -= mod; return *this; } mint& operator-=(const mint& a) { if ((x += mod-a.x) >= mod) x -= mod; return *this; } mint& operator*=(const mint& a) { (x *= a.x) %= mod; return *this; } mint operator+(const mint& a) const { mint res(*this); return res+=a; } mint operator-(const mint& a) const { mint res(*this); return res-=a; } mint operator*(const mint& a) const { mint res(*this); return res*=a; } mint pow(ll t) const { if (!t) return 1; mint a = pow(t>>1); a *= a; if (t&1) a *= *this; return a; } mint inv() const { return pow(mod-2); } mint& operator/=(const mint& a) { return (*this) *= a.inv(); } mint operator/(const mint& a) const { mint res(*this); return res/=a; } friend ostream& operator<<(ostream& os, const mint& m){ os << m.x; return os; } }; template struct Mat{ int h, w; vector> m, _m; Mat(int h, int w): h(h), w(w), m(h, vector(w)){} inline T& at(int i, int j) { return m[i][j]; } inline const T& at(int i, int j) const { return m[i][j]; } static Mat identity(int n){ Mat A(n, n); for(int i=0; i& operator+=(const Mat& B) { for(int i=0; i& operator-=(const Mat& B) { for(int i=0; i& operator*=(const Mat& B) { assert(w == B.h); _m.assign(h, vector(B.w)); for(int i=0; i pow(int n) { Mat A = identity(h); Mat B = *this; while(n > 0){ if(n & 1) A *= B; B *= B; n >>= 1; } return A; } }; int main(){ ios_base::sync_with_stdio(0); // finput("./input"); ll n; cin >> n; Mat m(6, 6); rep(i,6) m.at(0, i) = mint(6).inv(); rep(i,5) m.at(i+1, i) = mint(1); m = m.pow(n); cout << m.at(0, 0) << endl; return 0; }