分数: 800 点
问题陈述
Sig 建造了自己的键盘。该键盘专为极致简单而设计,仅具有 3 键就可以了: 0 键, 1 键和退格键。
首先,他使用带有此键盘的纯文本编辑器。该编辑器始终显示一个字符串(可能为空)。编辑器启动后,该字符串为空。当按下键盘上的每个键时,字符串会发生以下变化:
- 的
0键:一个字母0将被插入到字符串的右侧。 - 的
1键:一个字母1将被插入到字符串的右侧。 - 退格键:如果字符串为空,则不会发生任何情况。否则,删除字符串最右边的字母。
Sig 已启动编辑器,并按下了这些键 总共 N 次。结果,编辑器显示一个字符串 s。求这种按键方式的数量,取模 10^9 + 7.
约束
- 1 ≦ N ≦ 5000
- 1 ≦ |s| ≦ N
- s 由字母组成
0和1.
部分分数
- 400 通过满足以下条件的测试集将获得积分 1 ≦ N ≦ 300.
输入
输入由标准输入按以下格式给出:
N s
输出
打印按键的方式数 总共 N 次,以便编辑器显示字符串 s 最后,取模 10^9+7.
示例输入 1
3 0
示例输出 1
5
我们将退格键表示为 B.以下 5 按键方式将导致编辑器显示字符串 0 最后: 00B, 01B, 0B0, 1B0, BB0。最后一种方式,按下退格键时不会发生任何事情。
示例输入 2
300 1100100
示例输出 2
519054663
示例输入 3
5000 01000001011101000100001101101111011001000110010101110010000
示例输出 3
500886057