Little C excels in mathematics, so his teacher gave him a very difficult math assignment: Given positive integers $N$ and $M$, calculate the value of $Concatenate(1 \dots N) \pmod M$, where $Concatenate(1 \dots N)$ is the number obtained by concatenating all positive integers $1, 2, \dots, N$ in order. For example, if $N = 13$, $Concatenate(1 \dots N) = 12345678910111213$.

Little C thought about it for a long time and finally realized that this is a problem that cannot be solved by hand, so he has to ask for your help, hoping that you can write a program to solve this problem for him.

Input

The input contains two positive integers $N$ and $M$ separated by a space on a single line. For 30% of the data, $1 \le N \le 1000000$. For 100% of the data, $1 \le N \le 10^{18}$ and $1 \le M \le 10^9$.

Output

Output a single non-negative integer representing the value of $Concatenate(1 \dots N) \pmod M$.

Examples

Input 1

13 13

Output 1

4

Input 2

12345678910 1000000000

Output 2

345678910