公式解説では \(\displaystyle R_k=\sum_{i=0}^{k-1}10^k\) を \(M\times 10007\) で割ったあまりを前計算をして求めていますが、前計算をせずに簡単に計算する方法を紹介します。

\(\displaystyle f(N,x)=\sum_{i=0}^{N-1}x^i\) とします。求めたい値は \(f(k,10)\) です。

まず \(N=0\) の場合 \(f(0,x)=0\) です。

また、\(N\) が奇数の場合は \(i=0\) のみ別で考えることで \(f(N,x)=1+xf(N-1,x)\) となります。

さらに、 \(N\) が偶数の場合は \(i\) の偶奇を分けて考えることで

\[ \begin{aligned} &\phantom{=} f(N,x)\\ &=\sum_{i=0}^{N-1}x^i\\ &=\sum_{i=0}^{N/2-1}x^{2i}+\sum_{i=0}^{N/2-1}x^{2i+1}\\ &=(1+x)\sum_{i=0}^{N/2-1}x^{2i}\\ &=(1+x)f\left(N/2,x^2\right) \end{aligned} \]

が分かります。

以上を適宜 \(\text{mod}\) を取りながら再帰的に計算することで \(f(k,10)\) の値を求めることができます。計算量はダブリングと同じく \(O(\log k)\) です。

実装例(Python3)

k, m = map(int, input().split())
mod = 10007 * m

def f(n, x):
    if n == 0:
        return 0
    if n % 2:
        return (1 + x * f(n - 1, x)) % mod
    return (1 + x) * f(n // 2, x * x % mod) % mod

ans = 0
for i in range(k):
    c, l = map(int, input().split())
    ans = (pow(10, l, mod) * ans + c * f(l, 10)) % mod
print(ans // m)