AT_arc059_d [ARC059F] バイナリハック

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

N/A

N/A

### 制約 - $ 1\ ≦\ N\ ≦\ 5000 $ - $ 1\ ≦\ |s|\ ≦\ N $ - $ s $ は文字 `0`, `1` のみからなる。 ### 部分点 - $ 1\ ≦\ N\ ≦\ 300 $ を満たすデータセットに正解すると、$ 400 $ 点が与えられる。 ### Sample Explanation 1 バックスペースキーを `B` と表記すると、次の $ 5 $ 通りの押し方で最終的に表示される文字列が `0` となります: `00B`, `01B`, `0B0`, `1B0`, `BB0`。最後の押し方では、バックスペースキーを押すときに何も起こりません。