CCO Preparation Test 2 - Concatenation

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 0.6s
Memory limit: 128M

Problem types

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) = 12\,345\,678\,910. 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


Sample Input 2

12345678910 1000000000

Sample Output 2



There are no comments at the moment.