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\%~ of the test cases, ~1 \le N \le 1\,000\,000~.

In ~100\%~ 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) \pmod M~.

Sample Input 1

13 13

Sample Output 1

4

Sample Input 2

12345678910 1000000000

Sample Output 2

345678910