#include using namespace std; const long long int MOD = 1e9 + 7; const long long int mod = 1e9 + 7; using lint = long long; lint ipow(lint x, lint p){ lint ret = 1, piv = x; while(p){ if(p & 1) ret = ret * piv % mod; piv = piv * piv % mod; p >>= 1; } return ret; } vector berlekamp_massey(vector x){ vector ls, cur; int lf, ld; for(int i=0; i c(i-lf-1); c.push_back(k); for(auto &j : ls) c.push_back(-j * k % mod); if(c.size() < cur.size()) c.resize(cur.size()); for(int j=0; j=(int)cur.size()){ tie(ls, lf, ld) = make_tuple(cur, i, (t - x[i]) % mod); } cur = c; } for(auto &i : cur) i = (i % mod + mod) % mod; return cur; } int get_nth(vector rec, vector dp, lint n){ int m = rec.size(); vector s(m), t(m); s[0] = 1; if(m != 1) t[1] = 1; else t[0] = rec[0]; auto mul = [&rec](vector v, vector w){ int m = v.size(); vector t(2 * m); for(int j=0; j= mod) t[j+k] -= mod; } } for(int j=2*m-1; j>=m; j--){ for(int k=1; k<=m; k++){ t[j-k] += 1ll * t[j] * rec[k-1] % mod; if(t[j-k] >= mod) t[j-k] -= mod; } } t.resize(m); return t; }; while(n){ if(n & 1) s = mul(s, t); t = mul(t, t); n >>= 1; } lint ret = 0; for(int i=0; i x, lint n){ if(n < x.size()) return x[n]; vector v = berlekamp_massey(x); if(v.empty()) return 0; return get_nth(v, x, n); } struct elem{int x, y, v;}; // A_(x, y) <- v, 0-based. no duplicate please.. vector get_min_poly(int n, vector M){ // smallest poly P such that A^i = sum_{j < i} {A^j \times P_j} vector rnd1, rnd2; mt19937 rng(0x14004); auto randint = [&rng](int lb, int ub){ return uniform_int_distribution(lb, ub)(rng); }; for(int i=0; i gobs; for(int i=0; i<2*n+2; i++){ int tmp = 0; for(int j=0; j= mod) tmp -= mod; } gobs.push_back(tmp); vector nxt(n); for(auto &i : M){ nxt[i.x] += 1ll * i.v * rnd1[i.y] % mod; if(nxt[i.x] >= mod) nxt[i.x] -= mod; } rnd1 = nxt; } auto sol = berlekamp_massey(gobs); reverse(sol.begin(), sol.end()); return sol; } lint det(int n, vector M){ vector rnd; mt19937 rng(0x14004); auto randint = [&rng](int lb, int ub){ return uniform_int_distribution(lb, ub)(rng); }; for(int i=0; i v; vector dp = {6,40,213,1049,5034,23984,114069}; vector c = {9,-27,38,-29,11,1,-2}; int main(void) { cin.tie(0); ios::sync_with_stdio(false); long long int n; cin >> n; for(int i=7;i<=300;i++) { long long int sum = 0; for(int j=0;j<7;j++) { long long int val = c[j]*dp[i-1-j]; val%=mod; sum += val; sum%=mod; if(sum < 0) sum += mod; } dp.push_back(sum); } for(int i=0;i