$N$ はランレングス圧縮された形で与えられるので、圧縮区間ごとに以下のように順々に計算していくことができる。ここで、 $n_i$ を $i$ 番目の圧縮区間までの $N$ の値とし $(n_0 = 0)$ 、 $N = n_{K-1}$ とする。なお、以降は 0-indexed で考えることにする。

n_{i+1} = 10^{l_i} n_i + c_i \dfrac{10^{l_i} - 1}{9} \tag{2}

導出 (クリックして展開)

サンプルケース1で考えると、 $i = 3$ のとき、 $n_3 = 316, (c_3, l_3) = (2, 2)$ となる。

ここで、 $n_4 = 31622$ は以下のように分解できる。

\begin{align*} n_4 = 31622 & = 316 \times 10^2 + 22 \\ & = 316 \times 10^2 + 2 \times 11 \\ & = 316 \times 10^2 + 2 \times (10^0 + 10^1) \\ & = 316 \times 10^2 + 2 \times \frac{1 \times (10^2 - 1)}{10 - 1} \\ & = 316 \times 10^2 + 2 \times \frac{10^2 - 1}{9} \end{align*}

3行目から4行目への変形は、等比数列の和の公式を用いている。

これを一般化すると、式 $(2)$ が導出できる。

$\mathrm{mod}$ 演算では、和・差・積に関しては逐次的に計算していくことができるので、任意の法 $m$ に対して、以下のように計算することができる。

n_{i+1} \equiv 10^{l_i} n_i + c_i \dfrac{10^{l_i} - 1}{9} \pmod m

しかし、第2項には $9$ による割り算が含まれるので、そう単純に計算することはできない。それを次の2パターンに分けて考える。

$\mathrm{mod} = 10007 \: (m = 10007)$ の場合

このとき、 $10007$ は素数であるため、 $9$ と $10007$ は互いに素である。したがって、 $\mathrm{mod} \: 10007$ における $9$ の逆元 $9^{-1} = 1112$ を用いて、以下のように計算することができる。

n_{i+1} \equiv 10^{l_i} n_i + c_i \left( 10^{l_i} - 1 \right) \times 1112 \pmod{10007}

理由 (クリックして展開)

$\mathrm{mod} \: p$ における $x$ の逆元 $y = x^{-1}$ は、以下の式を満たす整数 $y$ である。

x y \equiv 1 \pmod p

この式に $x = 9, p = 10007$ を代入すると、

\begin{align*} 9 y & \equiv 1 \pmod{10007} \\ & = 10007 + 1 \\ y & = \frac{10008}{9} \\ & = 1112 \end{align*}

$\mathrm{mod} = M \: (m = M)$ の場合

$M$ は $1 \le M \le 10^4$ を満たす整数なので、この場合は $9$ と $M$ が互いに素とは限らないため、逆元が存在しない場合もある。

どうすればよいのだろうか？

とりあえず、求めたい余りを $y$ と置いてみる:

y \equiv \frac{10^l - 1}{9} \pmod M

ここで、 $\dfrac{10^l - 1}{9}$ を $M$ で割った商を $k$ とすると、

\begin{align*} \dfrac{10^l - 1}{9} & = k M + y \\ 10^l - 1 & = k (9M) + 9 y \end{align*}

となる。これは、「 $10^l - 1$ を $9M$ で割ると、商が $k$ で余りが $9y$ になる」ということを示しているから、

10^l - 1 \equiv 9y \pmod{9M}

と書ける。

今欲しいのは $y$ なので、次のように計算すればよい:

$10^l - 1$ を $9M$ で割った余りを計算する。
その結果を通常の除算として $9$ で割る。

以上により、式 $(1)$ は、3つの $\mathrm{mod}$ 演算を用いて、以下のように計算することができることが分かった。

$R = N \pmod M$ を $\mathrm{mod} \: M$ で計算する。
$N \pmod{M}$ の一部を $\mathrm{mod} \: 9M$ で計算する。
その他の部分を $\mathrm{mod} \: 10007$ で計算する。

実装例

ACLのmodint を用いることで、比較的容易に実装することができる。

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#if __has_include(<atcoder/all>)
5.#include <atcoder/all>
6.using namespace atcoder;
7.#endif
8. 
9.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
10. 
11.using ll = long long;
12. 
13.// ======================================== //
14. 
15.using mint = static_modint<10007>;
16.using mintM = dynamic_modint<1>;
17.using mint9M = dynamic_modint<2>;
18. 
19.int main()
20.{
21.    ll K, M;
22.    cin >> K >> M;
23.    vector<ll> c(K), l(K);
24.    rep(i, 0, K) cin >> c[i] >> l[i];
25.    mintM::set_mod(M);
26.    mint9M::set_mod(9 * M);
27. 
28.    mint N_mint = 0;
29.    mintM R = 0;
30.    rep(i, 0, K)
31.    {
32.        N_mint = N_mint * mint(10).pow(l[i]) + (c[i] * (mint(10).pow(l[i]) - 1) * mint(9).inv());
33.        ll r = (mint9M(10).pow(l[i]).val() - 1) / 9;
34.        R = R * mintM(10).pow(l[i]) + mintM(r) * c[i];
35.    }
36. 
37.    mint ans = (N_mint - R.val()) * mint(M).inv();
38.    cout << ans.val() << endl;
39. 
40.    return 0;
41.}