数学作业

【题目描述】

有这样一道数学作业：给定两个正整数N和M，询问Concatenate(1~N) mod M的值，其中Concatenate(1~N)表示将所有正整数1、2、······、N顺序连接得到的数。

例如N=13，Concatenate(1~N)=12345678910111213。

【输入描述】

输入两个正整数N和M。

【输出描述】

输出一个非负整数，表示Concatenate(1~N) mod M的值。

【样例输入】

13 13

【样例输出】

4

【数据范围及提示】

对于30%的数据，1 ≤ N ≤ 1000000；

对于100%的数据，1 ≤ N ≤ 10¹⁸，1 ≤ M ≤ 10⁹。