题目名称

数字拼接

题目描述

育华学校举办了一场数学挑战活动，以激发同学们对数学的兴趣和探索精神。在这次活动中，数学老师给同学们出了一道极具挑战性的题目。

已知育华学校有一系列编号从 $1$ 到 $n$ 的数学任务卡片。老师要求同学们将这些编号按照从小到大的顺序依次连接起来，形成一个巨大的数字。例如，当 $n = 13$ 时，连接后的数字就是 $12345678910111213$。

现在，老师给出两个正整数 $n$ 和 $m$，要求同学们计算将 $1$ 到 $n$ 所有正整数顺序连接起来得到的数（记为 $\text{Concatenate}(n)$ ）对 $m$ 取模的结果。

在众多同学中，小 C 向来以数学成绩优异著称，但面对这道难题，他苦思冥想许久，发现仅靠手动计算几乎是不可能完成的任务。于是，小 C 向你求助，希望你能编写一个程序帮他解决这个问题。

输入格式

一行包含两个正整数 $n$ 和 $m$。

输出格式

输出一行，包含一个整数，表示 $\text{Concatenate}(n) \bmod \ m$ 的结果。

输入输出样例 #1

输入 #1

13 13

输出 #1

4

说明/提示

【数据范围】

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