Informatica Online Judge

  Huge Integer! [3001 / 0BB9]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 3   Total Tried : 62


The Champion of this Problem (C++) : gs17068 - 76ms / 1662byte
My Best Submission (C++) : N/A

[IamCoder 0x23.8th 선발고사 (35th 윤교준)]

Background



$N$개의 정수, $B_1, B_2, ⋯, B_N$과 $N$개의 수열, $C_1, C_2, ⋯, C_N$에 대하여, $λ$를 다음과 같이 정의하자.


\lambda= {\overline{C_{1,1} C_{1,2}\cdots C_{1,B_1} C_{2,1} C_{2,2} \cdots C_{2,B_2} \cdots\cdots C_{N,1} C_{N,2} \cdots C_{N,B_N}}}_{\left(10\right)}


$1 ≤ i ≤ N$인 정수 $i$에 대하여, $C_{i,1} = C_{i,2} = ⋯ = C_{i,B_i} = A_i$를 만족할 때, $λ$를 $K$로 나눈 나머지를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 두 개의 정수 $N$과 $K$가 사이에 공백을 두고 주어진다.
두 번째 줄부터 $N$개의 줄에 걸쳐, $A$와 $B$의 정보가 주어진다.
$(i+1)$번째 줄에는 두 정수 $A_i$와 $B_i$가 사이에 공백을 두고 주어진다$(1 ≤ i ≤ N)$.
$1 ≤ i ≤ N$인 정수 $i$에 대하여, $0 ≤ A_i ≤ 9$와 $1 ≤ B_i ≤ 10^{18}$을 만족한다.
모든 입력 데이터에 대하여, $1 ≤ N ≤ 2 × 10^6$와 $1 ≤ K ≤ 5 × 10^5$을 만족한다.

Output

첫 번째 줄에 $λ$를 $K$로 나눈 나머지를 출력한다.

IO Example

입력
4 2
0 1
1 2
2 1
3 3

출력
1

설명
$λ =$ 0112333$_{\left(10\right)}$이므로, 이를 $K = 2$로 나눈 나머지인, $1$을 출력하여야 한다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]