题目描述

考虑以下游戏：

• 准备排成一列的 $N$ 个格子和大量石子。
• 初始时，在第 $i$ 个格子（$1 \leq i \leq N$）中放入 $a_i$ 个石子。
• 玩家可以重复进行以下操作：选择一个恰好有 $i$ 个石子的格子 $i$，将其中的所有石子取出，并在第 $1$ 到第 $i-1$ 个格子中各添加 $1$ 个石子。
• 最终剩余石子的总数即为得分。

对于长度为 $N$ 的数列 $a$，将该游戏进行后可能得到的最小得分记为 $f(a)$。

现在，对于所有长度为 $N$ 且每个元素在 $0$ 到 $K$ 之间的数列 $a$，求 $f(a)$ 的总和。由于答案可能非常大，请对 $1000000007$（即 $10^9+7$）取模。

输入格式

输入通过标准输入给出，格式如下：

$N$ $K$

输出格式

输出 $f(a)$ 的总和对 $1000000007$ 取模后的结果。

输入输出样例 #1

输入 #1

2 2

输出 #1

10

输入输出样例 #2

输入 #2

20 17

输出 #2

983853488

说明/提示

约束条件

• $1 \leq N \leq 100$
• $1 \leq K \leq N$

样例解释 1

当 $N=2$ 且 $K=2$ 时，共有 $9$ 种可能的数列 $a$，各数列对应的 $f(a)$ 值及操作示例如下：

• $f(\{0,0\})$：$0$（无法操作）
• $f(\{0,1\})$：$1$（无法操作）
• $f(\{0,2\})$：$0$（依次操作格子 $2$ 和格子 $1$）
• $f(\{1,0\})$：$0$（选择格子 $1$）
• $f(\{1,1\})$：$1$（选择格子 $1$）
• $f(\{1,2\})$：$0$（依次操作格子 $1$、格子 $2$、格子 $1$）
• $f(\{2,0\})$：$2$（无法操作）
• $f(\{2,1\})$：$3$（无法操作）
• $f(\{2,2\})$：$3$（选择格子 $2$）

翻译由 DeepSeek R1 完成