Bruce always comes up with new challenges for his students. On Saturday's class, Bruce gives Timothy two positive integers $N$ and $M$, and asks Timothy to calculate the $Concat(1,N)$ mod $M$, where $Concat(1,N)$ is the concatenation of all positive integers from $1$ to $N$. For example, $Concat(1,10)=12345678910$. Timothy is so smart that he immediately realizes that it is impossible to calculate the result by hand. Can you help Timothy to write a program to solve this question?

Input Specification

The input will consist of two integers, $N$ and $M$, in one line.

In $30\mathrm{\%}$ of the test cases, $1\le N\le 1000000$.

In $100\mathrm{\%}$ of the test cases, $1\le N\le {10}^{18}$ and $1\le M\le {10}^9$.

Output Specification

Output one integer, the result of $Concat(1,N)(\mathrm{mod}M)$.

Sample Input 1

13 13

Sample Output 1

4

Sample Input 2

12345678910 1000000000

Sample Output 2

345678910