Problem D: 核发电站

正确率: $12.20\%$ 下一题

Time Limit	$1$ 秒/Second(s)	Memory Limit	$512$ 兆字节/Megabyte(s)
提交总数	$41$	正确数量	$5$
裁判形式	标准裁判/Standard Judge	我的状态	尚未尝试
难度		分类标签	动态规划

Description

有N个位于一条直线上的城市，由于城市供电系统不足，城市设计师
想选择一些城市建设核发电站一供发电。现在有M种规模核发电站以
供选择，已知第K种规模核发电站的辐射半径是K。例如在第I座城市
建立第K种规模核发电站，一旦该城市的核发电站发生爆炸，那么[IK,I+K]区间内的城市都会受到辐射。假设此刻存在一些核发电站处于
辐射范围内，那么这些核发电站也会接连发生爆炸。
核发电站的安全需要技术人员来保障，而城市设计师的任务是选择合
适的建设方案，在设计上杜绝连锁爆炸的发生。现在城市设计师想咨
询你一共有多少个符合要求的设计方案。
注

Input

第一行输入整数 T，代表有 T组数据。
接下来每行代表一个数据，分别是 N(0<N<10000) ，M(0<M<100)

Output

对于每组数据，输出一行格式为 ‘Case t: x’ ，其中 t为数据组号，
x为方案数。由于过大，请输出对 1000000007 取余的结果。

Sample Input复制

2
3 2
4 2

Sample Output复制

Case 1: 8
Case 2: 15

提示

样例解释：对于第一组样例有以下八种方案数：

0 0 0；1 0 0；0 1 0；0 0 1；1 0 1；2 0 0；0 2 0；0 0 2；

0代表不建核发电站，数字1,2代表建造第1,2种规模核发电站。