题目描述

Sig建立了他自己的键盘。设计成极简风格，这个键盘上只有三个按键：0键，1键和回退键。

起初，他正在使用一个普通的文本编辑器和这个键盘。编辑器始终显示一个字符串（可能为空）。编辑器启动时，字符串为空。每按一次键盘上的按键，字符串会发生以下变化：

• 按下0键：在字符串右边插入字母0。
• 按下1键：在字符串右边插入字母1。
• 按下回退键：如果字符串为空，则什么也不发生。否则，删除字符串最右边的一个字符。

Sig已经启动了编辑器，并总共按下了这些按键$N$次。结果是编辑器显示了一个字符串$s$。求按下按键的方法数，对$10^9+7$取模。

约束条件

• $1 \leq N \leq 5000$
• $1 \leq |s| \leq N$
• $s$仅含有0和1两个字母。

部分分数

• 对于满足 $1 \leq N \leq 300$ 的测试集，将获得$400$分。

输入

输入的格式如下，从标准输入读入：

$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