问题描述

这是一个困难的数学问题；你的工作就是解决它。

给定两个整数 $N$ 和 $K$，我们有

$$A(N, K) = \{a \mid a = (a_1 a_2 a_3 \dots a_N), \text{其中 } a_i \text{ 是整数，} 0 \leq a_i \leq K-1, i = 1, \dots, N\}. $$

我们定义一个函数 $d = \text{Image}(a)$ 从 $A(N, K)$ 到 $A(N-1, K)$，如下所示：

对于任何 $a = (a_1 a_2 a_3 \dots a_N)$ 属于 $A(N, K)$，我们有

$$d = (d_1 d_2 \dots d_{N-1}) = \text{Image}(a),$$

其中 $d_i = \min(a_i, a_{i+1})$，即 $d_i$ 是 $a_i$ 和 $a_{i+1}$ 之间的较小值。

你应计算下面的表达式：

对于属于 $A(N, K)$ 的任何元素 $a$，表达式首先得到 $d = (d_1 d_2 \dots d_{N-1}) = \text{Image}(a)$；然后通过计算 $(d_1+1)(d_2+1)\dots(d_{N-1}+1)$ 来获得一个值。每个 $a$ 对应于一个值，而 $f(N, K)$ 只是这些值的总和。

例如，如果 $N = 2$，$K = 3$，则

$$A(N, K) = \{(00), (01), (02), (11), (10), (12), (20), (21), (22)\}; $$

从 $A(N, K)$ 中的每个元素获得的值是 $1, 1, 1, 2, 1, 2, 1, 2, 3$，我们可以知道 $f(2, 3) = 14$ 通过将这些值相加。

---

输入

输入仅包含一行，其中包含两个整数 $N$ 和 $K$：

• 如果 $N=2$，我们有 $1 \leq K \leq 5000$；
• 如果 $N=3$，我们有 $1 \leq K \leq 1000$；
• 如果 $N=4$，我们有 $1 \leq K \leq 500$。

---

输出

输出包含一个整数，即 $f(N, K)$ 的值。确认结果小于 $2^{63}$。

---

示例输入输出

输入 1

2 3

输出 1

14

---

源于

POJ Monthly,李学武