当前没有测试数据。

数学作业

题目描述

小$C$数学成绩优异，于是老师给小$C$留了一道非常难的数学作业题：

给定正整数$n$，$m$，要求计算$\text{cat}(n) \bmod m$的值，其中$\text{cat}(n)$是将$1 \sim n$所有正整数顺序连接起来得到的数。

例如，$n=13$，$\text{cat}(n)=12345678910111213$。小$C$想了大半天终于意识到这是一道不可能手算出来的题目，于是他只好向你求助，希望你能编写一个程序帮他解决这个问题。

输入格式

一行两个正整数$n$，$m$。

输出格式

输出一行一个整数表示答案。

数据范围与提示

• 对于$30\%$的数据，$1 \leq n \leq 10^{6}$；
• 对于$100\%$的数据，$1 \leq n < 10^{18}$，$1 \leq m \leq 10^{9}$。

样例

13 13

4

见homework2.in

见homework2.out