P11059 [Beginner Contest #27] Number (Hard Ver.)

> If I say I will not stop until I kiss you\ > Who can force me to settle\ > ——Li Ronghao, "Bu Jiang Jiu" In life, you cannot just “settle”. Whether you have made the best choice depends on each person.

You need to find an $n$-digit number $x$ that satisfies the following two conditions: - 1. The **remainder** of (**the sum of digits** of $x$) divided by $p$ is as small as possible. - 2. After condition 1 is satisfied, the value of $x$ is as small as possible. Sum of digits: the total obtained by adding the digits in every position of a number. For example, the sum of digits of $123$ is $1+2+3=6$.

The input consists of one line with two integers $n, p$.

Output one integer, representing the answer to the problem above.

#### Sample Explanation #1 Three-digit numbers include $100,101,\dots,999$. Among them, the sum of digits of $107$ is $1+0+7=8$, and the remainder of $8$ divided by $8$ is $0$. #### Constraints For $30\%$ of the testdata, $1 \le n \le 18$, $1 \le p \le 200$；\ For $100\%$ of the testdata, $1 \le n \le 10^6$, $1 \le p \le 10^9$。 Translated by ChatGPT 5