Digit Mapping Sum in K-ary Numbers

Given two integers (N) and (K) where (N \in {2,3,4}) and (2 \le K \le 6000), consider the set (A(N,K)) of all (N)-digit numbers in base (K) (with possible leading zeroes). For a number (a = a_1a_2\cdots a_N \in A(N,K)), define its image (d = d_1d_2\cdots d_{N-1}) by the mapping

[ Image(a) = d, \quad d_i = \min(a_i, a_{i+1}) \quad \text{for } i = 1,2,\dots, N-1. ]

Define the function

[ f(N,K) = \sum_{a \in A(N,K)} \left( \prod_{i=1}^{N-1}(d_i+1) \right), ]

where for each number (a) we compute its image (d=Image(a)) and then take the product ((d_1+1)(d_2+1)\cdots(d_{N-1}+1)).

For example, when (N=2) and (K=3), we have

( A(2,3)={00, 01, 02, 11, 10, 12, 20, 21, 22}, )

and

( \begin{array}{rcl} 00&:& \min(0,0)+1=1, \ 01&:& \min(0,1)+1=1, \ 02&:& \min(0,2)+1=1, \ 11&:& \min(1,1)+1=2, \ 10&:& \min(1,0)+1=1, \ 12&:& \min(1,2)+1=2, \ 20&:& \min(2,0)+1=1, \ 21&:& \min(2,1)+1=2, \ 22&:& \min(2,2)+1=3. \end{array} )

Thus, (f(2,3)=1+1+1+2+1+2+1+2+3=14).

Hint: A direct evaluation over (A(N,K)) will result in a timeout for most test cases. An efficient dynamic programming approach with prefix sums is required.

inputFormat

The input consists of a single line containing two space-separated integers (N) and (K).

outputFormat

Output the value of (f(N,K)) as defined above.

sample

2 3

14