[SCOI2006]k进制集合的映射

题目描述

设$A(N,K)$是全体$N$位$K$进制整数$a$的集合（$a$的高位可以为$0$，例如，$0023$可看作一个$4$位$8$进制数，或一个$4$位$5$进制数，由题中指定的条件可以唯一确定），其中$2≤K≤6000$，$N=2$，$3$，$4$，即:$$A(N,K)={a|a=a_1a_2a_3\cdots a_N,0≤a_i≤K-1,i=1,\cdots,N}$$

设$D(N-1,K)$是$A(N-1,K)$的一个子集，它是由$A(N,K)$生成的一个$N-1$位$K$进制整数$d$的集合，生成规则如下:

对任何$d\in D(N-1,K)$，存在$a\in A(N,K)$，使$d=Image(a)$，其中，$d=d_1d_2\cdots d_{N-1},d_i=min(a_i,a_{i+1})$，即$d_i$取为$a_i,a_{i+1}$的最小值。

注1：我们称这个规则为$A(N,K)$ 到$A(N-1,K)$内的一个映射$d=Image(a)$，可以证明这个映射是多对一的，即：如果$d,e\in D(N-1,k)$且$d\not=e$，则对任何满足$d=Image(a),e=Image(c)$的$A(N,K)$中的元素$a,c$，均有$a\not=c$

注2：对某些$K,N$, $D(N-1,K)$是$A(N-1,K)$的一个真子集，例如$K=4,N=4$，则不存在$a\in A(4,4)$，使$Image(a)=(323)$

任务：从文本文件输入两个用空格隔开的整数 $N,K$，然后在指定的文本文件中输出下列表达式的值：

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

上式表示对$A(N,K)$中的全部元素$a$，对其映像$d=Image(a)=d_1d_2\cdots d_{N-1}$的各位数字加$1$后的乘积求和。

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

例：设$N=2,K=3$，则$A(N,K)={00,01,02,11,10,12,20,21,22}$，正确的输出结果应为$14$。

提示：应先建立相应的计算方法，直接利用$f(N,K)$的表达式计算会使多数测试超时。

输入格式

输入文件只有一行：用空格隔开的两个整数N k。

输出格式

输出文件只有一个大整数，为计算结果。

样例 #1

样例输入 #1

2  3

样例输出 #1

14

提示

关于测试的说明：

数字完全正确，给满分。当输出结果的位数超过$15$位时，如果仅最后两位不准确时给一半分。（每个需测试的计算结果不超过$10^{19}$）。