题目描述

这是一个古老的打字机，只有三种操作，你需要打出所需的一个01串。

三种操作分别是1，0，B。

1和0表示在末尾增加一个1和0。

B表示删除末尾的一个字符。（如果当前串是空的则什么都不做）

下面告诉你要恰好进行 N 次操作。需要得到的串为 s。

请问有多少种操作方式可以得到所需的串。答案对 1e9+7 取模

输入

第一行一个整数 N。（1 ≤ N ≤ 5000） 第二行一个01串 s。（1 ≤ |s| ≤ N)

输出

一个整数，表示答案。

示例

input1

3
1

output1

5

限制

时间限制：1s 空间限制：128 MB