seuOJ570 - 孤独之歌

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：256 MiB
• 题目标签：Div.1, 2025 帆软杯

题目描述

拉普拉斯科算中心正在破解术士密码。

有三种操作。你的任务是用它们来打出给定的 01 串 $S$。

三种操作是 $\texttt{0}$、$\texttt{1}$ 和 $\texttt{B}$：

• 操作 $\texttt{0}$ 表示在末尾添加一个 $\texttt{0}$。
• 操作 $\texttt{1}$ 表示在末尾添加一个 $\texttt{1}$。
• 操作 $\texttt{B}$ 表示删除最后一个字符。特别地，若当前字符串为空，则什么也不做。

初始时，打字机上的字符串为空。

你需要进行恰好 $n$ 次操作，打出给定的 01 串 $S$。

求有多少个操作方案。答案对 $10^9+7$ 取模。

输入格式

第一行一个整数 $n$（$1\le n\le5000$）。

第二行一个 01 串 $S$（$1\le|S|\le n$）。

输出格式

一行一个整数，表示答案对 $10^9+7$ 取模后的结果。

样例

样例 1

输入

3
1

输出

5

解释

有 $5$ 个合法的操作方案：$\texttt{10B}$、$\texttt{11B}$、$\texttt{0B1}$、$\texttt{1B1}$、$\texttt{BB1}$。

样例 2

输入

9
110

输出

509