题目描述

しぐ制作了一款键盘。这款极致简约的键盘上只有 $3$ 个按键：0 键、1 键和退格键。

首先，しぐ打算用这款键盘操作一个简单的文本编辑器。编辑器始终显示一个字符串（也可能为空）。刚启动编辑器时，字符串为空。每按下一个按键，字符串会按如下方式变化：

• 0 键：在字符串的最右端插入字符 0。
• 1 键：在字符串的最右端插入字符 1。
• 退格键：如果字符串为空，则什么都不会发生；否则，删除字符串最右端的 $1$ 个字符。

しぐ启动编辑器后，总共按下了 $N$ 次按键。结果，现在编辑器上显示的字符串为 $s$。请你计算，有多少种按键顺序可以使得最终编辑器上显示的字符串为 $s$，并将答案对 $10^9+7$ 取模后输出。

输入格式

输入通过标准输入给出，格式如下：

$N\ s$

输出格式

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

样例 1

输入

3
0

输出

5

样例 2

输入

300
1100100

输出

519054663

样例 3

输入

5000
01000001011101000100001101101111011001000110010101110010000

输出

500886057

说明/提示

限制条件

• $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 翻译