#include using namespace std; typedef long long ll; #define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i) #define ALL(v) (v).begin(),(v).end() #define CLR(t,v) memset(t,(v),sizeof(t)) templateostream& operator<<(ostream& os,const pair&a){return os<<"("<void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<void chmin(T&a,const T&b){if(a>b)a=b;} templatevoid chmax(T&a,const T&b){if(a; using Matrix = vector; Matrix zero(int N){ return Matrix(N, Array(N)); } Matrix identity(int N) { Matrix A = zero(N); REP(i, N) A[i][i] = 1; return A; } Matrix add(const Matrix &A, const Matrix& B){ const int N = SZ(A); const int M = SZ(A[0]); Matrix C(N, Array(M)); REP(i, N) REP(j, M) { C[i][j] += A[i][j] + B[i][j]; if (C[i][j] >= MOD) C[i][j] %= MOD; } return C; } Array mul(const Matrix &A, const Array &x){ const int N = SZ(A); const int M = SZ(A[0]); Array y(N); REP(i, N) REP(j, M) y[i] += A[i][j] * x[j]; return y; } // A:[N,P] * B:[P,M] = C:[N,M] Matrix mul(const Matrix &A, const Matrix& B) { const int N = SZ(A); const int P = SZ(A[0]); const int M = SZ(B[0]); Matrix C(N, Array(M)); REP(i, N) REP(j, M) REP(k, P) { C[i][j] += A[i][k] * B[k][j]; if (C[i][j] >= MOD) C[i][j] %= MOD; } return C; } // O ( n^3 log e ) // Matrix pow(const Matrix& A, ll e) { // return e == 0 ? identity(SZ(A)) : // e % 2 == 0 ? pow( mul(A,A) , e/2 ) : mul(A, pow(A,e-1)); // } Matrix pow(Matrix A, ll b) { Matrix C = identity(SZ(A)); while (b > 0) { if ((b & 1) == 1) C = mul(C, A); A = mul(A, A); b >>= 1; } return C; } void print(const Matrix& A){ REP(i, SZ(A)){ REP(j, SZ(A[0])){ cout << A[i][j] << " "; } cout << endl; } cout << "---------------------" << endl; } ll ways(ll n) { Matrix A = zero(4); A[0][0] = 10; A[0][1] = 1; A[1][1] = 1; Array b(2); b[0] = 1; b[1] = 1; if (n == 0) { return 0; } A = pow(A, n-1); b = mul(A, b); return b[0]; } Array ways(ll L, ll R) { ll l = ways(L); ll r = ways(R); Array w(10); for (int i = 1; i <= 9; i++) w[i] = ((r - l) % MOD + MOD) % MOD; w[0] = 1; return w; } const int MAX_N = 112345; ll dp[MAX_N][10]; int main2() { CLR(dp, 0); int N = nextLong(); vector L(N), R(N), D(N); REP(i, N) L[i] = nextLong(); REP(i, N) R[i] = nextLong(); REP(i, N) D[i] = nextLong(); dp[0][0] = 1; for (int i = 0; i < N; i++) { auto w = ways(L[i], R[i]); // cout << "w="; pv(ALL(w)); for (int j = 0; j < 10; j++) { for (int k = 0; k < 10; k++) { if (dp[i][j] == 0) continue; int nj = (j + k) % 9; if (nj == 0) { if (j == 0 && k == 0) nj = 0; else nj = 9; } (dp[i+1][nj] += (dp[i][j] * w[k]) % MOD) %= MOD; } } // for (int j = 0; j < 10; j++) {cout << dp[i+1][j] << " "; } cout << endl; for (int j = 0; j < 10; j++) { if (D[i] != j) dp[i+1][j] = 0; } } ll ans = 0; for (int j = 0; j < 10; j++){ ans += dp[N][j]; } cout << ans << endl; return 0; } int main() { // int L = 1; // int R = 2; // { // vector v(10); // v[0] = 1; // for (int i = pow(10, L); i < pow(10, R); i++) { // int r = i % 9; // if (r == 0) r = 9; // ++v[r]; // } // pv(ALL(v)); // } // auto x = ways(L, R); // pv(ALL(x)); // return 0; #ifdef LOCAL for (;!cin.eof();cin>>ws) #endif main2(); return 0; }