#include using namespace std; #define mod 1000000007 template class matrix { protected: vector< vector > _mat; int _col, _row; const bool usingModulo = true; const Numeric modulo = 1000000007; // using modulo void resize(int col, int row) { _col = col; _row = row; _mat.assign(col, vector(row, 0)); } public: matrix(int col, int row) : _col(col), _row(row) { _mat.assign(col, vector(row, 0)); } matrix(int col, int row, int num) : _col(col), _row(row) { _mat.assign(col, vector(row, num)); } int col() const { return _col; } int row() const { return _row; } vector &operator[](int i) { return _mat[i]; } Numeric &operator() (int i, int j) { return _mat[i][j]; } matrix operator+(matrix &x) { if (this->col() != x.col() || this->row() != x.row()) { cout << "matrices are different sizes .. "; this->size(false); cout << "+"; x.size(true); exit(0); } matrix ret(this->col(), this->row()); for (int i = 0; i < this->col(); ++i) { for (int j = 0; j < this->row(); ++j) { ret[i][j] = _mat[i][j] + x[i][j]; if (usingModulo) ret[i][j] %= modulo; } } return ret; } matrix &operator+=(matrix &x) { if (this->col() != x.col() || this->row() != x.row()) { cout << "matrices are different sizes .. "; this->size(false); cout << "+"; x.size(true); exit(0); } for (int i = 0; i < this->col(); ++i) { for (int j = 0; j < this->row(); ++j) { _mat[i][j] += x[i][j]; if (usingModulo) _mat[i][j] %= modulo; } } return *this; } matrix operator-(matrix &x) { if (this->col() != x.col() || this->row() != x.row()) { cout << "matrices are different sizes .. "; this->size(false); cout << "-"; x.size(true); exit(0); } matrix ret(this->col(), this->row()); for (int i = 0; i < this->col(); ++i) { for (int j = 0; j < this->row(); ++j) { ret[i][j] = _mat[i][j] - x[i][j]; if (usingModulo) ret[i][j] %= modulo; } } return ret; } matrix &operator-=(matrix &x) { if (this->col() != x.col() || this->row() != x.row()) { cout << "matrices are different sizes .. "; this->size(false); cout << "-"; x.size(true); exit(0); } for (int i = 0; i < this->col(); ++i) { for (int j = 0; j < this->row(); ++j) { _mat[i][j] -= x[i][j]; if (usingModulo) _mat[i][j] %= modulo; } } return *this; } matrix operator*(matrix &x) { if (this->row() != x.col()) { cout << "cannot multiply matrices .. "; this->size(false); cout << "*"; x.size(true); exit(0); } matrix ret(this->col(), x.row()); for (int i = 0; i < this->col(); ++i) { for (int j = 0; j < x.row(); ++j) { for (int k = 0; k < this->row(); ++k) { ret[i][j] += _mat[i][k] * x[k][j]; if (usingModulo) ret[i][j] %= modulo; } } } return ret; } matrix &operator*(Numeric k) { matrix ret(this->col(), this->row()); for (int i = 0; i < this->col(); ++i) { for (int j = 0; j < this->row(); ++j) { ret(i, j) = _mat[i][j] * k; if (usingModulo) ret(i, j) %= modulo; } } return ret; } matrix &operator*=(matrix &x) { if (this->row() != x.col()) { cout << "cannot multiply matrices .. "; this->size(false); cout << "*"; x.size(true); exit(0); } matrix ret(this->col(), x.row()); for (int i = 0; i < this->col(); ++i) { for (int j = 0; j < x.row(); ++j) { for (int k = 0; k < this->row(); ++k) { ret[i][j] += _mat[i][k] * x[k][j]; if (usingModulo) ret[i][j] %= modulo; } } } this->resize(this->col(), x.row()); for (int i = 0; i < this->col(); ++i) { for (int j = 0; j < x.row(); ++j) { _mat[i][j] = ret[i][j]; } } return *this; } matrix &operator*=(Numeric k) { matrix ret(this->col(), this->row()); for (int i = 0; i < this->col(); ++i) { for (int j = 0; j < this->row(); ++j) { _mat[i][j] *= k; if (usingModulo) _mat %= modulo; } } return *this; } void print() { cout << "-- print "; this->size(false); cout << " --" << endl; for (int i = 0; i < _col; ++i) { for (int j = 0; j < _row; ++j) { if (j != 0) cout << "\t"; cout << _mat[i][j]; } cout << endl; } cout << "------------------" << endl; } void print(string str) { cout << "-- print \"" << str << "\" "; this->size(false); cout << " --" << endl; for (int i = 0; i < _col; ++i) { for (int j = 0; j < _row; ++j) { if (j != 0) cout << "\t"; cout << _mat[i][j]; } cout << endl; } cout << "------------------" << endl; } void size (bool endline = true) const { cout << "(" << this->col() << ", " << this->row() << ")"; if (endline) cout << endl; } }; template class squareMatrix : public matrix { private: public: squareMatrix(int col): matrix(col, col){ } squareMatrix(int col, int num): matrix(col, col, num) { } squareMatrix(int col, bool identity): matrix(col, col) { if (identity) { for (int i = 0; i < col; ++i) { this->_mat[i][i] = 1; } } } }; int main(){ int n; cin >> n; matrix ans(1, 10, 0), mat(10, 10, 0); for (int i = 0; i < 10; ++i) { for (int j = i; j < 10; ++j) { mat[i][j] = 1; } } ans[0][0] = 1; while (n > 0) { if (n % 2 == 1) { ans *= mat; } n /= 2; mat *= mat; } long long sum = 0; for (int i = 0; i < 10; i++) { sum += ans[0][i]; sum %= mod; } cout << sum << endl; }