#include #include #include #include #include #include #include #include #include #include using namespace std; #define MOD 1000000007 //[n*p] * [p*m] => [n*m] template vector< vector > multmat(const vector > &A, const vector> &B, int n, int p, int m){ vector > C(n, vector(m,0)); for(int i=0; i vector< vector > mat_pow(vector > A, long long k){ int n = A.size(); vector > ret(n, vector(n, 0) ); for(int i=0; i0){ if(k&1) ret = multmat(A,ret, n,n,n); A = multmat(A,A, n,n,n); k>>=1; } return ret; } template ostream& operator << (ostream& os, vector vec){ for(int i=0; i> n; vector> mat = { {0,0,1}, {1,0,0}, {1,1,0} }; auto mat_ = mat_pow(mat, n); //cerr << mat_ << endl; cout << (mat_[0][2]+mat_[1][2]+mat_[2][2])%MOD << endl; return 0; }