menu ZJOJ
account_circle 请登录
home
首页
book
题目
apps
分类
play_circle_outline
状态
assessment
竞赛
assignment
作业
equalizer
排名
assignment_ind
登录
person_add
注册
1216: News 39
时间限制:1.000s
内存限制:128MB

题目描述

现在插播一条新闻。

现在有条长度为 M 米的隧道,进去的人都遇到了鬼打墙。有人从入口开始,向前走走停停了 N 秒(行走时步行速度每秒一米,停止时每秒0米,在每一秒内要么行走,要么停止),没有走出隧道,反而又回到了原处,真可怕。

现在我台发现了该隧道的秘密——人在隧道内每走一米,有一定概率发生前后空间置换,即前变后,后变前。

现在,回到原点的人想知道,有多少种可能的空间置换使得他回到了原点?

由于可能的方案数过大,请将结果 mod 10^9+7 后再告诉他。

输入格式

输入 N,M

输出格式

输出 返回方案数 mod 10^9+7

样例输入 content_copy

3 2

样例输出 content_copy

4

提示/说明

样例说明:

初始位置0
1) 未发生空间置换,发生空间置换,停止
未发生空间置换: 位置+1,当前在1
发生空间置换: 位置-1,当前在0
停止:位置不变,当前在0
2) 停止,未发生空间置换,发生空间置换
停止:位置不变,当前在0
未发生空间置换: 位置+1,当前在1
发生空间置换: 位置-1,当前在0
3) 未发生空间置换,停止,发生空间置换
未发生空间置换: 位置+1,当前在1
停止:位置不变,当前在1
发生空间置换: 位置-1,当前在0
4) 停止,停止,停止
停止:位置不变,当前在0
停止:位置不变,当前在0
停止:位置不变,当前在0

注意,由于未走出隧道,位置既不可能 <= -1,也不可能 >= m


更多测试数据:

输入2 4输出2
输入4 2输出8

分类