[ARC059F] バイナリハック

小z得到了一个键盘，里面只有$1, 0$和退格键 键$0$可以打出一个$0$的字符串，键$1$同理 退格键可以删除前面打出的那个字符 小z可以操作这个键盘$N$次（$N\le5000$），求操作完成后打出来的字符串恰好是$S$的方案数 注意：当前没有字符也可以使用退格键

[problemUrl]: https://atcoder.jp/contests/arc059/tasks/arc059_d しぐはキーボードを製作しました。シンプルさを極限まで追求したこのキーボードには、`0` キー、`1` キー、バックスペースキーの $ 3 $ つしかキーがありません。 手始めに、しぐはこのキーボードで簡単なテキストエディタを操作してみることにしました。このエディタには常に一つの文字列が表示されます（文字列が空のこともあります）。エディタを起動した直後では、文字列は空です。キーボードの各キーを押すと、文字列が次のように変化します。 - `0` キー: 文字列の右端に文字 `0` が挿入される。 - `1` キー: 文字列の右端に文字 `1` が挿入される。 - バックスペースキー: 文字列が空なら、何も起こらない。そうでなければ、文字列の右端の $ 1 $ 文字が削除される。 しぐはエディタを起動し、これらのキーを合計で $ N $ 回押しました。その結果、いまエディタに文字列 $ s $ が表示されています。このようなキーの押し方の個数を $ 10^9\ +\ 7 $ で割った余りを求めてください。

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

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

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`。最後の押し方では、バックスペースキーを押すときに何も起こりません。