Problem Description

Calculate the remainder when the integer $ N $ is divided by $ M $.

However, $ N $ is very large and is given in the following format:

Format: $ K $ characters $ C_i $ and $ K $ positive integers $ D_i $ are given. Let $ S_i $ be the string formed by concatenating $ D_i $ copies of character $ C_i $. Then, $ N $ is the integer represented in base 10 by the string formed by concatenating $S_1, \ldots, S_K$ in this order.

Input Format

The input is given from the standard input in the following format:

$ K $ $ M $ $ C_1 $ $ D_1 $ $\vdots$ $ C_K $ $ D_K $

Output Format

Output the answer.

Sample Input and Output

Sample Input #1

3 11
1 4
2 2
3 1

Sample Output #1

3

Sample Input #2

2 10000
1 1
0 1000000000000

Sample Output #2

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

Notes/Hints

Constraints

• $2 \leq M \leq 10^9$
• $1 \leq K \leq 10^5$
• $ C_i $ is a digit from 0 to 9
• $ C_1 $ is not 0
• $1 \leq D_i \leq 10^{12}$
• All values included in the input are integers

Sample Explanation 1

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

Sample Explanation 2

$ N $ is the number with a 1 followed by $ 10^{12} $ zeros. The remainder when $ N $ is divided by $ 10000 $ is $ 0 $.

见题面 Input 部分

见题面 Output 部分