P3216 [HNOI2011] Math Homework

Xiao C excels in math, so the teacher assigned him a very difficult math homework problem: Given positive integers $n,m$, compute $\text{Concatenate}(n) \bmod \ m$, where $\text{Concatenate}(n)$ is the number obtained by concatenating all positive integers $1 \sim n$ in order. For example, $n = 13$, $\text{Concatenate}(n) = 12345678910111213$. After thinking for a long time, Xiao C realized that this problem is impossible to work out by hand, so he asks you to write a program to solve it for him.

One line with two positive integers $n,m$.

Output one integer on a single line representing the answer.

Constraints For $30\%$ of the testdata, $1\le n \le 10^6$. For $100\%$ of the testdata, $1\le n \le 10^{18}$, $1\le m \le 10^9$. - On 2023.4.20, one set of hack testdata was added. Translated by ChatGPT 5