#include using namespace std; 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> p; vector a(3001); a[0] = 0; a[1] = 0; a[2] = 1; for(int i=3;i<=3000;i++) { long long int val = a[i-2]; val += ((p*a[i-1])%mod); val%=mod; a[i] = val; } vector b; b.push_back(0); b.push_back(0); for(int i=2;i<=3000;i++) { long long int temp = 0; for(int j=1;j> Q; for(int i=0;i> q; cout << guess_nth_term(b,q) << '\n'; } return 0; }