User's AC Ratio

61.1% (11/18)

Submission's AC Ratio

17.0% (15/88)

Description

小酉鬼是一位熱愛數學的高中生,他總是喜歡「走到哪、算到哪」,像是將經過的公車號碼質因數分解,或是觀察樓梯的階數是否為卡特蘭數。

雖然小酉鬼數學很好,但他的數學考試總是不及格,因為──他字寫太醜了……
他總是把$9$寫得像$5$、把$3$寫得像$2$……

有一天,小酉鬼的數學老師終於受不了了,於是要求他罰寫印度-阿拉伯數字,從$1$寫到$N$,當然字寫很醜的小酉鬼是沒有學過「空格」或「換行」的,所以寫出來的罰寫大約長這樣:

$12345678910111213\dots$

,如果把它看成一個數字,表示為$f(N)$。

正當小酉鬼罰寫到一半時,他突然想求$f(N)$除以$M$的餘數。但因為他忙著罰寫,所以請你幫他求出解答。

例如,若$N=5,M=6$,則$f(N)=12345$,$12345$除以$6$的餘數是$3$;若$N=2,M=17$,則$f(N)=12$,$12$除以$17$的餘數是$12$。

Input Format

輸入檔可能包含多筆測試資料(最多$5000$),每筆測試資料中會有兩個正整數$N(1 \leq N < 10^ 9)$,$M(1 \leq M \leq 10^ 4)$。

子任務(測資) 額外限制 分數
1 (0~2) $N \leq 9$ 5
2 (3~7) $N \leq 10^ 6$ 25
3 (8~15) 70

Output Format

對於每組測試資料,請輸出一個數字,代表$f(N)$除以$M$的餘數。

Sample Input

5 6
2 17

Sample Output

3
12

Hints

Problem Source

Problem Set by Ting.H

Subtasks

For Testdata: 0 ~ 2, Score: 5
For Testdata: 0 ~ 7, Score: 25
For Testdata: 0 ~ 15, Score: 70
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144
2 1000 65536 262144
3 1000 65536 262144
4 1000 65536 262144
5 1000 65536 262144
6 1000 65536 262144
7 1000 65536 262144
8 1000 65536 262144
9 1000 65536 262144
10 1000 65536 262144
11 1000 65536 262144
12 1000 65536 262144
13 1000 65536 262144
14 1000 65536 262144
15 1000 65536 262144