TopCoder

User's AC Ratio

66.7% (16/24)

Submission's AC Ratio

19.6% (21/107)

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

No. Testdata Range Score
1 0~2 5
2 0~7 25
3 0~15 70

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1 2 3
1 1000 65536 262144 1 2 3
2 1000 65536 262144 1 2 3
3 1000 65536 262144 2 3
4 1000 65536 262144 2 3
5 1000 65536 262144 2 3
6 1000 65536 262144 2 3
7 1000 65536 262144 2 3
8 1000 65536 262144 3
9 1000 65536 262144 3
10 1000 65536 262144 3
11 1000 65536 262144 3
12 1000 65536 262144 3
13 1000 65536 262144 3
14 1000 65536 262144 3
15 1000 65536 262144 3