#pragma GCC optimize ("O3") #pragma GCC target ("avx") #include "bits/stdc++.h" // define macro "/D__MAI" using namespace std; typedef long long int ll; #define debugv(v) printf("L%d %s => ",__LINE__,#v);for(auto e:v){cout< ",__LINE__,#m);for(int x=0;x<(w);x++){cout<<(m)[x]<<" ";}cout< ostream& operator <<(ostream &o, const pair p) { o << "(" << p.first << ":" << p.second << ")"; return o; } #define TIME chrono::system_clock::now() #define MILLISEC(t) (chrono::duration_cast(t).count()) namespace { std::chrono::system_clock::time_point ttt; void tic() { ttt = TIME; } void toc() { fprintf(stderr, "TIME : %lldms\n", MILLISEC(TIME - ttt)); } std::chrono::system_clock::time_point tle = TIME; #ifdef __MAI void safe_tle(int msec) { assert(MILLISEC(TIME - tle) < msec); } #else #define safe_tle(k) ; #endif } #ifdef __MAI #define getchar_unlocked getchar #define putchar_unlocked putchar #endif #ifdef __VSCC #define getchar_unlocked _getchar_nolock #define putchar_unlocked _putchar_nolock #endif namespace { #define isvisiablechar(c) (0x21<=(c)&&(c)<=0x7E) class MaiScanner { public: template void input_integer(T& var) { var = 0; T sign = 1; int cc = getchar_unlocked(); for (; cc<'0' || '9'>(int& var) { input_integer(var); return *this; } inline MaiScanner& operator>>(long long& var) { input_integer(var); return *this; } inline MaiScanner& operator>>(string& var) { int cc = getchar_unlocked(); for (; !isvisiablechar(cc); cc = getchar_unlocked()); for (; isvisiablechar(cc); cc = getchar_unlocked()) var.push_back(cc); } }; } MaiScanner scanner; template //typedef double T; class matrix { public: size_t height, width; valarray data; matrix(size_t height, size_t width) :height(height), width(width), data(height*width) {} matrix(size_t height, size_t width, const valarray& data) :height(height), width(width), data(data) {} inline T& operator()(size_t y, size_t x) { return data[y*width + x]; } inline T operator() (size_t y, size_t x) const { return data[y*width + x]; } inline T& at(size_t y, size_t x) { return data[y*width + x]; } inline T at(size_t y, size_t x) const { return data[y*width + x]; } inline void resize(size_t h, size_t w) { height = h; width = w; data.resize(h*w); } inline void fill(T val) { data = val; } matrix& setDiag(T val) { for (size_t i = 0, en = min(width, height); i < en; ++i)at(i, i) = val; return *this; } inline bool issquare() const { return height == width; } void print(ostream& os) { os << "- - -" << endl; // << setprecision(3) for (size_t y = 0; y < height; ++y) { for (size_t x = 0; x < width; ++x) { os << setw(7) << at(y, x) << ' '; }os << endl; } } template void copyto2d(MT& d2) { for (size_t i = 0; i < width*height; ++i) { d2[i / width][i%width] = data[i]; } } // mathematics matrix pow(long long); double det() const; T tr(); matrix& transpose_self(); matrix transpose() const; struct LU { size_t size; vector pivot; vector elem; }; }; // IO template inline ostream& operator << (ostream& os, matrix mat) { mat.print(os); return os; } // 掛け算 template matrix multiply(const matrix& mat1, const matrix& mat2) { assert(mat1.width == mat2.height); matrix result(mat1.height, mat2.width); for (size_t i = 0, j, k; i < mat1.height; i++) { for (j = 0; j < mat2.width; j++) { for (k = 0; k < mat1.width; k++) { result(i, j) += mat1(i, k) * mat2(k, j); } } } return result; } template valarray multiply(const matrix& mat1, const valarray& vec2) { assert(mat1.width == vec2.size()); valarray result(mat1.height); for (size_t i = 0, j; i < mat1.height; i++) { for (j = 0; j < mat1.width; j++) { result[i] += mat1(i, j) * vec2[j]; } } return result; } template inline matrix& operator*=(matrix& mat1, matrix& mat2) { mat1 = multiply(mat1, mat2); return mat1; } template inline matrix operator*(matrix& mat1, matrix& mat2) { return multiply(mat1, mat2); } // スカラー template inline matrix& operator+=(matrix& mat, T val) { mat.data += val; return mat; } template inline matrix& operator*=(matrix& mat, T val) { mat.data *= val; return mat; } template inline matrix& operator/=(matrix& mat, T val) { mat.data /= val; return mat; } template inline matrix& operator^=(matrix& mat, T val) { mat.data ^= val; return mat; } // 行列 template inline matrix& operator+=(matrix& mat1, matrix& mat2) { mat1.data += mat2.data; return mat1; } template inline matrix operator+(matrix& mat1, matrix& mat2) { return matrix(mat1.height, mat1.width, mat1.data + mat2.data); } // べきじょう template matrix matrix::pow(long long p) { assert(issquare()); matrix a = *this; matrix b(height, height); b.setDiag(1); while (0 < p) { if (p % 2) { b *= a; } a *= a; p /= 2; } return b; } class llmod { public: const ll MOD = MD; private: ll val; inline ll cut(ll v) const { return ((v%MOD) + MOD) % MOD; } public: llmod() : MOD(MD), val(0) {} llmod(ll num, ll m = MD) : MOD(m), val(cut(num)) {} llmod(const llmod& lm, ll m) : MOD(m), val(lm.val) {} inline ll operator*() const { return val; } inline llmod& operator=(const llmod& lm) { val = lm.val; return *this; } inline llmod& operator=(ll v) { val = cut(v); return *this; } inline llmod& operator+=(ll v) { val = cut(val + v); return *this; } inline llmod& operator+=(const llmod& l) { val = cut(val + l.val); return *this; } inline llmod& operator-=(ll v) { val = cut(val - v); return *this; } inline llmod& operator-=(const llmod& l) { val = cut(val - l.val); return *this; } inline llmod& operator*=(ll v) { val = cut(val * v); return *this; } inline llmod& operator*=(const llmod& l) { val = cut(val * l.val); return *this; } inline llmod& operator++() { val = (val + 1) % MOD; return *this; } inline llmod operator++(int) { llmod t = *this; val = (val + 1) % MOD; return t; } }; ostream& operator<<(ostream& os, const llmod& l) { os << *l; return os; } inline llmod operator+(llmod t, const llmod& r) { return t += r; } inline llmod operator-(llmod t, const llmod& r) { return t -= r; } inline llmod operator*(llmod t, const llmod& r) { return t *= r; } // MEMO : 逆元...powm(n,MD-2) llmod pow(llmod x, ll p) { llmod y = 1; while (0 < p) { if (p % 2) y *= x; x *= x; p /= 2; } return y; } inline llmod& operator/=(llmod& l, const llmod& r) { return l *= pow(r, r.MOD - 2); } int main() { ll n; cin >> n; matrix matz(10, 10, valarray{ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1 }); valarray stat = valarray{ 1,0,0,0,0,0,0,0,0,0 }; matz = matz.pow(n + 1); valarray rslt = multiply(matz, stat); cout << *rslt[9] << endl; return 0; }