Description

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.

Input Format

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

Output Format

Output one integer on a single line representing the answer.

13 13

4

Hint

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