P5128 Good Times.

# If you do not want to spend too much time reading the statement, please scroll to the bottom of the page to see the simplified version. Time flies. Time is like running water, constantly washing over everything. In the blink of an eye, the third year of junior high has arrived. A huge amount of homework and tense exams leave Xiao L and Xiao K less and less time to prepare for NOIP.

The unavoidable day finally came. Xiao L sat alone in the classroom, staring out the window in a daze. The playground was not finished yet, the sky was empty, and the afterglow of the sunset had just painted a trace of blood-red beside the gray high-rises, then vanished in an instant without leaving any mark. The rustling autumn wind blew in through the window, and the classroom filled with the sound of pages turning. The book was flipped to a page with the doodles that Xiao L and Xiao K had drawn together. A crumpled score slip rolled back and forth on the desk like a hard-to-untie knot. There was not a single star in the sky—perhaps because of the dark clouds in his heart that could not be blown away. Xiao L did terribly on the monthly exam for general subjects, and the NOIP preliminary round also went extremely poorly. It was very likely that he would not make it to the next round. As for those dark clouds that could not be blown away, let them stay there. Anyway, there was no chance to change anything. If it were not for the stressful pace of the third year, perhaps everyone would not have gone their separate ways so easily. One former teammate after another left the computer room. Sigh, I will probably have to leave the computer room too, Xiao L thought. At that moment, he remembered every good time he had spent with Xiao K. From the upright figures during the military training in the first year, to the two voices arguing fiercely in front of the podium, to the depressing scenes at the provincial contest, and to the days and nights they struggled together in the computer room... Thinking of those good times made his heart feel warm. He felt that every second with Xiao K was worth cherishing. Then Xiao K came to Xiao L, learned about Xiao L’s wish, and Xiao L wanted to assign a “value worth cherishing” to every second he spent with Xiao K. If he added up all these values, Xiao L would keep all those good times in his heart, and his mood would get better. Xiao L computes the value of a time moment like this: he first numbers each second sequentially starting from $1$, then converts the time (this second number) into the hour-minute-second form. For some reason, one minute for Xiao L has only $k$ seconds (a joke should be here), so Xiao L thinks that one hour also has only $k$ minutes. You may regard this as converting the second number into base $k$. Since Xiao L is not that evil, $k$ is always an integer here. Then he looks at this base-$k$ number and finds the length of the longest consecutive arithmetic progression inside it (only considering the case of a consecutive interval made up of single digits; that is, something like $123456789101112$ in base $10$ cannot be considered an arithmetic progression), and he records this length as the value of that second. Xiao K really wants to help compute the total value of these seconds (from second $1$ to second $n$) to comfort the sad Xiao L. But the total number of seconds $n$ is far, far too large, so large that Xiao K would need more than one second to compute the value of a single second, and then the time Xiao L and Xiao K spend together could be **extended infinitely**. Xiao L very much hopes for that, but clearly they do not have that much time. Xiao K found you, who are proficient in $OI$. To avoid the second number increasing during computation, you need to compute the answer within $1$ second. Since the answer may be very large, Xiao L accepts the result modulo $19260821$. ## Simplified statement: Given $n,k$, compute $\sum_{i=1}^n f(i,k)$, where $f(i,k)$ is defined as follows: write the decimal integer $i$ in base $k$ as a sequence of digits, and take the length of the longest contiguous substring that forms an arithmetic progression. Output the answer modulo $19260821$. ## Some extra words Because Xiao L was driven to study general subjects, the expanded story part of this statement is “to be continued”!

One line with two integers $n$ and $k$. The input $n$ is given in decimal.

One line with one integer: the sum of values modulo $19260821$.

Explanation for sample $\#1$: $1$ to $5$ in base $3$ are $1,2,10,11,12$. The value of each number is exactly its length, so the total value is $1+1+2+2+2=8$. For $10\%$ of the testdata, $1\le n\le 10^6,k=60$. For another $10\%$ of the testdata, $k=10$. For $40\%$ of the testdata, $2\le k\le 20,1\le n\le k^{10}$. For $100\%$ of the testdata, $2\le k\le 60,1\le n\le k^{18}$. **There are no subtasks (no gradient in the data)!!!** # Xiao L teaches you math **Arithmetic progression**: An arithmetic progression is a sequence in which, starting from the second term, the difference between each term and the previous term is the same constant. This constant is called the common difference of the arithmetic progression. **The common difference can be any real number.** That is, the sequence may be increasing, decreasing, or constant (common difference $0$). Translated by ChatGPT 5