F - Unhappy Hacking Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 800 点

問題文

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

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

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

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

制約

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

部分点

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

入力

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

N
s

出力

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

入力例 1

3
0

出力例 1

5

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

入力例 2

300
1100100

出力例 2

519054663

入力例 3

5000
01000001011101000100001101101111011001000110010101110010000

出力例 3

500886057

Score : 800 points

Problem Statement

Sig has built his own keyboard. Designed for ultimate simplicity, this keyboard only has 3 keys on it: the 0 key, the 1 key and the backspace key.

To begin with, he is using a plain text editor with this keyboard. This editor always displays one string (possibly empty). Just after the editor is launched, this string is empty. When each key on the keyboard is pressed, the following changes occur to the string:

  • The 0 key: a letter 0 will be inserted to the right of the string.
  • The 1 key: a letter 1 will be inserted to the right of the string.
  • The backspace key: if the string is empty, nothing happens. Otherwise, the rightmost letter of the string is deleted.

Sig has launched the editor, and pressed these keys N times in total. As a result, the editor displays a string s. Find the number of such ways to press the keys, modulo 10^9 + 7.

Constraints

  • 1 ≦ N ≦ 5000
  • 1 ≦ |s| ≦ N
  • s consists of the letters 0 and 1.

Partial Score

  • 400 points will be awarded for passing the test set satisfying 1 ≦ N ≦ 300.

Input

The input is given from Standard Input in the following format:

N
s

Output

Print the number of the ways to press the keys N times in total such that the editor displays the string s in the end, modulo 10^9+7.

Sample Input 1

3
0

Sample Output 1

5

We will denote the backspace key by B. The following 5 ways to press the keys will cause the editor to display the string 0 in the end: 00B, 01B, 0B0, 1B0, BB0. In the last way, nothing will happen when the backspace key is pressed.

Sample Input 2

300
1100100

Sample Output 2

519054663

Sample Input 3

5000
01000001011101000100001101101111011001000110010101110010000

Sample Output 3

500886057