Problem Background

If you don't want to spend too much time reading the problem, please scroll to the bottom of the page to view the concise version of the problem statement.

Time flies like an arrow, and the sun and moon move like a shuttle. Time flows like water, constantly eroding everything. Before we know it, the third year of junior high has arrived. The massive amount of homework and the intense exams are leaving less and less time for Xiao L and Xiao K to prepare for NOIP...

Problem Description

The inevitable day has come, and Xiao L sits alone in the classroom, staring out the window.

The playground is still under construction, the sky is empty, and the last rays of the setting sun just painted a streak of blood red beside the gray high-rise buildings, disappearing instantly without leaving a trace. The autumn wind blows in through the window, and the rustling sound of pages being turned fills the classroom. The book is turned to the page where Xiao L and Xiao K drew their shared graffiti. The crumpled report card rolls around on the desk like an unsolvable knot. There isn't a single star in the sky—probably because of the unshakable clouds in the heart.

Xiao L's monthly exam in liberal arts has gone terribly, and the preliminary round of NOIP was extremely unsatisfactory, likely preventing him from advancing to the finals.

As for the unshakable clouds in the heart, let them be there, since there's no chance to change anything anyway.

If it weren't for the intense pace of the third year, everyone probably wouldn't have parted so easily, right? One by one, former teammates leave the computer room.

Alas, I guess I'll have to leave the computer room too, Xiao L thinks.

At this moment, he recalls every good time spent with Xiao K.

From the upright figures during the military training in the first year, to the two voices engaged in heated discussions in front of the podium, the颓废 scenes during the provincial competition, and the days and nights spent striving together in the computer room...

Recalling these good times, his heart feels warm. He feels that every second spent with Xiao K is a precious moment worth cherishing.

At this moment, Xiao K comes to Xiao L's side, knowing Xiao L's wish. Xiao L wants to calculate a value worth cherishing for every second spent with Xiao K. If these values are all added together, Xiao L will remember these good times in his heart, and his mood will improve.

Xiao L calculates the value of a moment as follows: He first numbers each second sequentially from $1$, then converts the time (the number of seconds) into hours-minutes-seconds format. For some reason, Xiao L's minute has only $k$ seconds (here should be a wry smile), so Xiao L thinks an hour also has only $k$ minutes. You can consider Xiao L converting the number of seconds into a $k$-ary system. Since Xiao L is not that malicious, $k$ here is always an integer. Then he observes this $k$-ary number, finds the length of the longest continuous arithmetic sequence (considering only the case of a single digit forming a continuous interval, that is, a sequence like $123456789101112$ in decimal cannot be considered an arithmetic sequence), and records it as the value of that second.

Xiao K really wants to help him calculate the total value of these seconds (from $1$ second to $n$ seconds) to comfort the sad Xiao L. However, the total number of seconds $n$ is too long, and it takes Xiao K more than a second to calculate the value of one second, thus allowing Xiao L and Xiao K's time together to be extended infinitely. Xiao L really hopes for this, but obviously, they don't have that much time.

Xiao K finds you, who are proficient in OI. To avoid the number of seconds increasing during the calculation, you need to calculate the answer within one second. Since the answer may be very large, Xiao L is willing to accept the result modulo $19260821$.

Input Format

The input consists of a single line with two integers $n$ and $k$. The input $n$ is in decimal representation.

Output Format

The output consists of a single line with an integer, which is the sum of the values modulo $19260821$.

Sample Input and Output

Sample Input #1

5 3

Sample Output #1

8

Sample Input #2

99 10

Sample Output #2

189

Sample Input #3

377377377377 60

Sample Output #3

139733

Notes

Explanation for Sample #1:

From $1$ to $5$ converted to base $3$ are $1, 2, 10, 11, 12$, each number's value is exactly its length, so the total value is $1 + 1 + 2 + 2 + 2 = 8$.

For $10\%$ of the data, $1 \le n \le 10^6, k = 60$;

For another $10\%$ of the data, $k = 10$;

For $40\%$ of the data, $2 \le k \le 20, 1 \le n \le k^{10}$;

For $100\%$ of the data, $2 \le k \le 60, 1 \le n \le k^{18}$.

The data has no gradient!!!

Xiao L Teaches You Math

Arithmetic Sequence: An arithmetic sequence is a sequence in which each term after the first differs from the preceding term by a constant difference, called the common difference. The common difference can be any real number. That is, the sequence can be increasing, decreasing, or constant (with a common difference of $0$).

Concise Version of the Problem Statement:

Given $n, k$, find the value of $\sum_{i=1}^n f(i, k)$, where $f(i, k)$ is defined as the length of the longest continuous substring in the $k$-ary representation of the decimal integer $i$ that forms an arithmetic sequence. The answer should be taken modulo $19260821$.

见题面 Input 部分

见题面 Output 部分