← 返回题目列表

AtCoder · arc059_d

F. 不愉快的黑客攻击

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

分数: 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