//何も考えなければ、上の桁から途中まで作った数をnとして dp[n mod 7] : 何通り? とすればOK. //10^3 ≡ (-1) mod 7 を使うことで、L_i <-- L_i % 6していいので、あとは簡単。 //なお、等比級数の和はmod 7の逆元が存在しないことがあるので、使えない。 //modが一般ならダブリングを使うという手がある。 #include #define int long long #define rep(i, n) for(i = 0; i < n; i++) using namespace std; int mod = 1000000007; int n; int d[100000], L[100000]; int dp[100001][7]; int p10[6] = {1, 10, 100, 1000, 10000, 100000}; int repunit[6] = {0, 1, 11, 111, 1111, 11111}; signed main() { int i, j; cin >> n; rep(i, n) { cin >> d[i] >> L[i]; L[i] %= 6; } dp[0][0] = 1; rep(i, n) { rep(j, 7) { dp[i + 1][j] += dp[i][j]; dp[i + 1][j] %= mod; int nj = (j * p10[L[i]] + repunit[L[i]] * d[i]) % 7; dp[i + 1][nj] += dp[i][j]; dp[i + 1][nj] %= mod; } } int ans = 0; rep(i, 7) { ans += dp[n][i] * i; ans %= mod; } cout << ans << endl; return 0; }