시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 173 34 15 60.000%

문제

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

$\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}}}_{(10)}$

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

입력

첫번째 줄에 두 개의 정수 $N$과 $K$가 사이에 공백을 두고 주어진다.

두번째 줄부터 $N$개의 줄에 걸쳐, $A$와 $B$의 정보가 주어진다.

$(i+1)$번째 줄에는 두 정수 $A_i$와 $B_i$가 사이에 공백을 두고 주어진다$(1 \le i \le N)$.

$1 \le i \le N$인 정수 $i$에 대하여, $0 \le A_i \le 9$와 $1 \le B_i \le 10^{18}$을 만족한다.

모든 입력 데이터에 대하여, $1 \le N \le 2 \times 10^6$와 $1 \le K \le 5 \times 10^5$을 만족한다.

출력

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

서브태스크 1 (50점)

$\left(\Sigma_{i=1}^{N}B_i\right) \le 10^6$을 만족한다.

서브태스크 2 (50점)

추가적인 제약은 없다.

예제 입력 1

4 2
0 1
1 2
2 1
3 3

예제 출력 1

1

첫번째 입출력 예제는 $\lambda = \overline{0112333}_{(10)}$이므로, 이를 $K = 2$로 나눈 나머지인, $1$을 출력하여야 한다.

출처

  • 문제를 만든 사람: yclock

채점

  • 예제는 채점하지 않는다.