#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 d[100005]; int n; vector v[10]; long long int dp[31][10]; int main(void) { cin.tie(0); ios::sync_with_stdio(false); cin >> n; for(int i=0;i> L[i]; } for(int i=0;i> R[i]; } for(int i=0;i> D[i]; if(D[i]==0) { cout << 0 << '\n'; return 0; } } d[0].push_back(D[0]); for(int i=1;i 0) { x += (temp%10); temp/=10; } dp[i+1][x] += dp[i][j]; dp[i+1][x]%=MOD; } } } for(int i=0;i<10;i++) { long long int sum = 0; for(int j=0;j<=30;j++) { sum += dp[j][i]; sum%=MOD; v[i].push_back(sum); } } long long int res = 1; for(int i=0;i