配点 : $800$ 点

問題文

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

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

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

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

制約

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

部分点

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

入力

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

$N$

$s$

出力

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

3
0

5

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

300
1100100

519054663

5000
01000001011101000100001101101111011001000110010101110010000

500886057