CCO Preparation Test 2 - Concatenation

View as PDF

Submit solution

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

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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

Comments

There are no comments at the moment.