#J3017. News 39
News 39
题目描述
现在插播一条新闻。现在有条长度为 M 米的隧道,进去的人都遇到了鬼打墙。有人从入口开始,向前走走停停了 N 秒(行走时步行速度每秒一米,停止时每秒0米,在每一秒内要么行走,要么停止),没有走出隧道,反而又回到了原处,真可怕。
现在我台发现了该隧道的秘密——人在隧道内每走一米,有一定概率发生前后空间置换,即前变后,后变前。
现在,回到原点的人想知道,有多少种可能的空间置换使得他回到了原点?
由于可能的方案数过大,请将结果 mod 10^9+7 后再告诉他。
输入格式
输入 N,M输出格式
输出 返回方案数 mod 10^9+73 24
提示
样例说明:
初始位置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