Description

Let $A(N,K)$ be the set of all $N$-digit base-$K$ integers $a$ (the most significant digit of $a$ may be $0$; for example, $0023$ can be regarded as a $4$-digit base-$8$ number or a $4$-digit base-$5$ number. Under the conditions specified in the problem, it can be uniquely determined), where $2 \le K \le 6000$ and $N = 2, 3, 4$. That is,

$$A(N,K)={a|a=a_1a_2a_3\cdots a_N,0≤a_i≤K-1,i=1,\cdots,N}$$

Let $D(N-1,K)$ be a subset of $A(N-1,K)$. It is the set of $(N-1)$-digit base-$K$ integers $d$ generated from $A(N,K)$. The generation rule is as follows:

For any $d \in D(N-1,K)$, there exists $a \in A(N,K)$ such that $d = Image(a)$, where $d = d_1d_2\cdots d_{N-1}$ and $d_i = min(a_i,a_{i+1})$. That is, $d_i$ is the smaller one of $a_i$ and $a_{i+1}$.

Note 1: We call this rule a mapping from $A(N,K)$ to $A(N-1,K)$, written as $d = Image(a)$. It can be proven that this mapping is many-to-one. That is, if $d,e \in D(N-1,k)$ and $d \not= e$, then for any elements $a,c \in A(N,K)$ satisfying $d = Image(a)$ and $e = Image(c)$, we have $a \not= c$.

Note 2: For some $K,N$, $D(N-1,K)$ is a proper subset of $A(N-1,K)$. For example, when $K=4,N=4$, there does not exist any $a \in A(4,4)$ such that $Image(a)=(323)$.

Task: Read two integers $N,K$ separated by a space from the input text file, and then output the value of the following expression to the specified output text file:

$$f(N,K)=\sum_{a\in A(N,K),Image(a)=d}(\prod_{i=1}^{N-1}(d_i+1))$$

The expression above means: for all elements $a$ in $A(N,K)$, let its image be $d = Image(a) = d_1d_2\cdots d_{N-1}$, add $1$ to each digit of $d$, take the product, and then sum these products.

Where

$$\prod^{N-1}_{i=1}(d_i+1)=(d_1+1)(d_2+1)\cdots(d_{N-1}+1)$$

Example: Let $N=2,K=3$. Then $A(N,K)={00,01,02,11,10,12,20,21,22}$, and the correct output should be $14$.

Hint: You should first build a suitable method for computation. Directly computing using the expression of $f(N,K)$ will cause most testdata to time out.

Input Format

The input file contains only one line: two integers $N$ and $K$ separated by a space.

Output Format

Output a single big integer, which is the computed result.

2  3

14

Hint

About the tests:

Full marks are given if the number is completely correct. When the number of digits of the output exceeds $15$, if only the last two digits are incorrect, half of the score is given. (Each required result does not exceed $10^{19}$.)

Translated by ChatGPT 5