#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> mat() const {return _mat; } vector &operator[](int i) { return _mat[i]; } Numeric &operator() (int i, int j) { return _mat[i][j]; } Matrix &operator=(Matrix x) { this->_mat = x.mat(); 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->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; } Numeric sum() { Numeric ret = 0; for (int i = 0; i < this->col(); ++i) { for (int j = 0; j < this->row(); ++j) { ret += _mat[i][j]; if (usingModulo) ret %= modulo; } } return ret; } 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; long long k; cin >> n >> k; Matrix ans(n, 1, 1), a(n, n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> a[i][j]; } } while (k) { if (k & 1) { ans = a * ans; } a *= a; k /= 2; } cout << ans.sum() << endl; return 0; } */ int main() { long long n; cin >> n; if (n < 8) { cout << 1; for (int i = 0; i < n; i++) { cout << 3; } cout << endl; return 0; } Matrix a(2, 2, 0), b(2, 2, 0), c(2, 1); a[0][0] = a[0][1] = 1; a[1][1] = 10; c[0][0] = 1; c[1][0] = 10; b = a; long long ans = 0; long long k = n-2; while (k) { if (k & 1) { c = a * c; } a *= a; k /= 2; } ans += c.sum() * 2 % mod; c = b * c; ans = (ans + c.sum()) % mod; cout << ans << endl; return 0; }