题目背景

这是 $CSP-J$ 模拟赛的 $T4$ 。

题目描述

小$C$得到了一个键盘，里面只有 $1, 0$ 和退格键。

键$0$可以打出一个 $0$ 的字符串，键 $1$ 同理。

退格键可以删除前面打出的那个字符。

小$C$可以操作这个键盘 $N$ 次（ $N\le5000$ ），求操作完成后打出来的字符串恰好是 $S$ 的方案数。

注意：当前没有字符也可以使用退格键。

输入格式

输入两行。

第一行输入一个整数 $N$ 表示操作次数。

第二行一个字符串 $S$ ,字符串中只包含 $0,1$ 两种字符。

输出格式

输出一行。

输出一个整数表示方案数模 $1000000007$ 意义下的结果。

样例 #1

样例输入 #1

3
0

样例输出 #1

5

样例 #2

样例输入 #2

300
1100100

样例输出 #2

519054663

样例 #3

样例输入 #3

5000
01000001011101000100001101101111011001000110010101110010000

样例输出 #3

500886057

提示

样例解释】：

对于第一个样例，小$C$可以先退格两次再敲上一个 $0$ ，可以敲一个任意字符再删除再敲 $0$ ，还可以敲一个 $0$ ，再敲一个任意字符再删除。

数据范围】：

$|S|$ 是 $S$ 的长度。

对于 $10 \% 的数据$ ，$|S|=N$

对于另外 $10 \%$ 的数据，$|S| = N + 2$

对于另外 $20 \%$ 的数据，$1 \le |S| \le N \le 8$

对于另外 $30 \%$ 的数据，$1 \le |S| \le N \le 200$

对于 $100 \%$ 的数据，$1 \le |S| \le N \le 5000$ ， $S$ 中仅包含字符 $0,1$