[HNOI2011] 数学作业

题目描述

小 C 数学成绩优异,于是老师给小 C 留了一道非常难的数学作业题: 给定正整数 $n,m$,要求计算 $\text{Concatenate}(n) \bmod \ m$ 的值,其中 $\text{Concatenate}(n)$ 是将 $1 \sim n$ 所有正整数 顺序连接起来得到的数。 例如,$n = 13$,$\text{Concatenate}(n) = 12345678910111213$。小 C 想了大半天终于意识到这是一道不可能手算出来的题目,于是他只好向你求助,希望你能编写一个程序帮他解决这个问题。

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

13 13

输出样例 #1

4

说明

【数据范围】 对于 $30\%$ 的数据,$1\le n \le 10^6$; 对于 $100\%$ 的数据,$1\le n \le 10^{18}$,$1\le m \le 10^9$。 - 2023.4.20 添加一组 hack 数据。