L - N mod M Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

問題文

整数 N を M で割った余りを求めてください。

ただし、N は非常に大きいため、次のような形式で与えられます。

形式：K 個の文字 C_i と K 個の正整数 D_i が与えられる。S_i を「文字 C_i を D_i 個繋げた文字列」とするとき、S_1,\ldots,S_N をこの順に繋げた文字列を 10 進法で表された整数とみなしたものが N である。

制約

  • 2\leq M \leq 10^9
  • 1 \leq K \leq 10^5
  • C_i は 0 から 9 の数字
  • C_1 は 0 でない
  • 1\leq D_i \leq 10^{12}
  • 入力に含まれる値は全て整数である

入力

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

K M
C_1 D_1
\vdots
C_K D_K

出力

答えを出力せよ。

入力例 1

3 11
1 4
2 2
3 1

出力例 1

3

N=1111223 です。N を 11 で割った余りは 3 です。

入力例 2

2 10000
1 1
0 1000000000000

出力例 2

0

N は 1 の後ろに 0 が 10^{12} 個つく数です。N を 10000 で割った余りは 0 です。

入力例 3

8 5054049
1 41421356
1 7320508075
2 2360679
3 141592653589
0 57721566
1 644934066848
2 99792458
9 192631770

出力例 3

3689688

Score : 6 points

Problem Statement

Find the remainder when an integer N is divided by M.

Since N is enormous, it is given to you in the format below.

Format: You are given K characters C_i and K positive integers D_i. Let S_i be the concatenation of D_i copies of the character C_i. N is the concatenation of S_1,\ldots,S_N in this order, seen as a decimal integer.

Constraints

  • 2\leq M \leq 10^9
  • 1 \leq K \leq 10^5
  • C_i is a digit between 0 and 9 (inclusive).
  • C_1 is not 0.
  • 1\leq D_i \leq 10^{12}
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

K M
C_1 D_1
\vdots
C_K D_K

Output

Print the answer.

Sample Input 1

3 11
1 4
2 2
3 1

Sample Output 1

3

We have N=1111223. The remainder when N is divided by 11 is 3.

Sample Input 2

2 10000
1 1
0 1000000000000

Sample Output 2

0

N is written as 1 followed by 10^{12} zeros. The remainder when N is divided by 10000 is 0.

Sample Input 3

8 5054049
1 41421356
1 7320508075
2 2360679
3 141592653589
0 57721566
1 644934066848
2 99792458
9 192631770

Sample Output 3

3689688