N-Concatenation

Interview

Time limit1.5sMemory limit1024 MB

Summary

Given N and K, find the remainder when the concatenation 123...N of the integers 1 through N is divided by K.

Level: Easy3 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

In base 10, the number $\overline{123\cdots N}$ formed by writing the positive integers $1$ , $2$ , $3$ , $\cdots$ , $N$ in order is called the $N$ -concatenation. For example, $12345$ is the $5$ -concatenation, and $12345678910111213$ is the $13$ -concatenation. Given $N$ and an integer $K$ , find the remainder when the $N$ -concatenation is divided by $K$ .

Input

The first line contains integers $N$ and $K$ separated by a space. ( $1 \le N \le 10^7$ , $1 \le K \le 10^9$ )

Output

Print the remainder when the $N$ -concatenation is divided by $K$ on the first line.

Examples3

Example 1
Input
```
5 7
```
Expected output
```
4
```
Example 2
Input
```
10000000 1
```
Expected output
```
0
```
Example 3
Input
```
10000000 12341234
```
Expected output
```
11927308
```