← 返回题目列表

AtCoder · cf17_final_g

G. 曼卡拉

中文机器翻译题面 查看原题

分数: 1000 点

问题陈述

考虑以下游戏:

  • 游戏是使用一排 N 正方形和许多石头。
  • 首先, a_i 石头被放入广场 i\ (1 \leq i \leq N).
  • 玩家可以根据需要多次执行以下操作:“选择一个整数 i 使得广场 i 恰好包含 i 石头。移除广场上的所有石头 i,并为每个添加一颗石头 i-1 来自 Square 的方块 1 到广场 i-1."
  • 玩家的最终得分是方格中剩余石子的总数。

对于序列 a 长度 N,让 f(a) 是玩游戏时可以获得的最低分数 a.

求总和 f(a) 所有序列 a 长度 N 其中每个元素位于 0 和 K (含)。 由于它可能非常大,因此求模答案 1000000007 (= 10^9+7).

约束

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

输入

输入由标准输入按以下格式给出:

N K

输出

打印总和 f(a) 模数 1000000007 (= 10^9+7).


示例输入 1

2 2

示例输出 1

10

有九个长度的序列 2 其中每个元素位于 0 和 2。对于他们每个人来说,价值 f(a) 以及如何实现如下:

  • f(\{0,0\}): 0 (无能为力)
  • f(\{0,1\}): 1 (无能为力)
  • f(\{0,2\}): 0 (选择方块 2,然后 Square 1)
  • f(\{1,0\}): 0 (选择方块 1)
  • f(\{1,1\}): 1 (选择方块 1)
  • f(\{1,2\}): 0 (选择方块 1,方形 请回答下面的 2,然后 Square 1)
  • f(\{2,0\}): 2 (无能为力)
  • f(\{2,1\}): 3 (无能为力)
  • f(\{2,2\}): 3 (选择方块 2)

示例输入 2

20 17

示例输出 2

983853488