AT_arc059_d [ARC059F] バイナリハック

しぐ制作了一款键盘。这款极致简约的键盘上只有 $3$ 个按键：`0` 键、`1` 键和退格键。 首先，しぐ打算用这款键盘操作一个简单的文本编辑器。编辑器始终显示一个字符串（也可能为空）。刚启动编辑器时，字符串为空。每按下一个按键，字符串会按如下方式变化： - `0` 键：在字符串的最右端插入字符 `0`。 - `1` 键：在字符串的最右端插入字符 `1`。 - 退格键：如果字符串为空，则什么都不会发生；否则，删除字符串最右端的 $1$ 个字符。 しぐ启动编辑器后，总共按下了 $N$ 次按键。结果，现在编辑器上显示的字符串为 $s$。请你计算，有多少种按键顺序可以使得最终编辑器上显示的字符串为 $s$，并将答案对 $10^9+7$ 取模后输出。

输入通过标准输入给出，格式如下： > $N\ s$

输出能够使最终编辑器上显示字符串 $s$ 的 $N$ 次按键顺序的方案数，对 $10^9+7$ 取模。

## 限制条件 - $1\leq N\leq 5000$ - $1\leq |s|\leq N$ - $s$ 仅由字符 `0` 和 `1` 组成 ## 部分分 - 对于 $1\leq N\leq 300$ 的数据集，满分为 $400$ 分。 ## 样例说明 1 用 `B` 表示退格键，以下 $5$ 种按键顺序最终会显示字符串 `0`：`00B`、`01B`、`0B0`、`1B0`、`BB0`。在最后一种方案中，按下退格键时字符串为空，因此不会发生任何变化。 由 ChatGPT 4.1 翻译