E - Simple Division Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

整数 N,M が与えられるので、 \lfloor N/M \rfloor を \color{red}{10007} で割った余りを求めてください。
ここで、 \lfloor x \rfloor は x 以下で最大の整数を表します。 例えば、 \lfloor 3.14 \rfloor=3, \lfloor 10 \rfloor = 10 です。

但し、この問題では N は直接与えられず、ランレングス圧縮された形で与えられます。
具体的には、 N は K 個の「数字 c_i と整数 l_i の組」からなる列で表現されます。
元の N を復元するには、以下の手順を用います。

  • 最初、文字列 S を空文字列とする。
  • i=1,2,\dots,K について、以下を繰り返す。
    • S の末尾に数字 c_i を l_i 個付け加える。
  • 最終的な S をひとつの整数として解釈したとき、その整数が N である。

制約

  • 1 \le M \le 10^4
  • 1 \le K \le 10^5
  • c_i は 0,1,2,3,4,5,6,7,8,9 いずれかの数字
  • 1 \le l_i \le 10^9
  • c_1 \neq 0
  • M,K,l_i は整数

入力

入力は以下の形式で標準入力から与えられる。

K M
c_1 l_1
c_2 l_2
\vdots
c_K l_K

出力

答えを出力せよ。

入力例 1

6 7
3 1
1 1
6 1
2 2
7 2
6 2

出力例 1

3797

この入力では N=316227766,M=7 です。
\lfloor 316227766/7 \rfloor = 45175395 であり、これを 10007 で割った余りである 3797 が最終的な答えとなります。

入力例 2

1 1
1 1

出力例 2

1

入力例 3

10 9999
9 419921892
9 923650333
6 476449815
1 8837775
2 141135534
5 462618481
3 202652735
0 771538044
4 321458589
0 570032864

出力例 3

8437

Score : 450 points

Problem Statement

You are given integers N and M. Find the remainder when \lfloor N/M \rfloor is divided by \color{red}{10007}.
Here, \lfloor x \rfloor denotes the largest integer not exceeding x. For example, \lfloor 3.14 \rfloor=3 and \lfloor 10 \rfloor = 10.

In this problem, N is not given directly; instead, it is given in run-length encoded form.
Specifically, N is represented by a sequence of K pairs of a digit c_i and an integer l_i.
To recover the original N, use the following procedure.

  • Initially, let string S be the empty string.
  • For i=1,2,\dots,K, repeat the following.
    • Append l_i copies of digit c_i to the end of S.
  • Interpret the final S as a single integer; that integer is N.

Constraints

  • 1 \le M \le 10^4
  • 1 \le K \le 10^5
  • c_i is one of the digits 0,1,2,3,4,5,6,7,8,9.
  • 1 \le l_i \le 10^9
  • c_1 \neq 0
  • M,K,l_i are integers.

Input

The input is given from Standard Input in the following format:

K M
c_1 l_1
c_2 l_2
\vdots
c_K l_K

Output

Output the answer.

Sample Input 1

6 7
3 1
1 1
6 1
2 2
7 2
6 2

Sample Output 1

3797

In this input, N=316227766 and M=7.
\lfloor 316227766/7 \rfloor = 45175395, and the remainder when this is divided by 10007 is 3797, which is the final answer.

Sample Input 2

1 1
1 1

Sample Output 2

1

Sample Input 3

10 9999
9 419921892
9 923650333
6 476449815
1 8837775
2 141135534
5 462618481
3 202652735
0 771538044
4 321458589
0 570032864

Sample Output 3

8437