题目描述

しぐはキーボードを製作しました。シンプルさを極限まで追求したこのキーボードには、0 キー、1 キー、バックスペースキーの $3$ つしかキーがありません。

手始めに、しぐはこのキーボードで簡単なテキストエディタを操作してみることにしました。このエディタには常に一つの文字列が表示されます（文字列が空のこともあります）。エディタを起動した直後では、文字列は空です。キーボードの各キーを押すと、文字列が次のように変化します。

• 0 キー: 文字列の右端に文字 0 が挿入される。
• 1 キー: 文字列の右端に文字 1 が挿入される。
• バックスペースキー: 文字列が空なら、何も起こらない。そうでなければ、文字列の右端の $1$ 文字が削除される。

しぐはエディタを起動し、これらのキーを合計で $N$ 回押しました。その結果、いまエディタに文字列 $s$ が表示されています。このようなキーの押し方の個数を $10^9\ +\ 7$ で割った余りを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $s$

输出格式

最終的にエディタに文字列 $s$ が表示されるような $N$ 回のキーの押し方の個数を $10^9+7$ で割った余りを出力せよ。

题目大意

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

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

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

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

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

3
0

5

300
1100100

519054663

5000
01000001011101000100001101101111011001000110010101110010000

500886057

提示

制約

• $1\ ≦\ N\ ≦\ 5000$
• $1\ ≦\ |s|\ ≦\ N$
• $s$ は文字 0, 1 のみからなる。

部分点

• $1\ ≦\ N\ ≦\ 300$ を満たすデータセットに正解すると、$400$ 点が与えられる。

Sample Explanation 1

バックスペースキーを B と表記すると、次の $5$ 通りの押し方で最終的に表示される文字列が 0 となります: 00B, 01B, 0B0, 1B0, BB0。最後の押し方では、バックスペースキーを押すときに何も起こりません。