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-----
3
0

-----Sample Output-----
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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'import sys\ninput = sys.stdin.readline\n\nimport numpy as np\n\n"""\n0,1の配置は関係ない。文字列長だけが問題。\n"""\n\nMOD = 10**9 + 7\nN = int(input())\nS = input().rstrip()\n\nLS = len(S)\n\n# 長さ、何通り\ndp = np.zeros(N+1, dtype=np.int64)\ndp[0] = 1\nfor _ in range(N):\n    prev = dp\n    dp = np.zeros_like(prev)\n    # 文字の追加\n    dp[1:] += 2*prev[:-1]\n    # 文字の削除\n    dp[:-1] += prev[1:]\n    dp[0] += prev[0]\n    dp %= MOD\n\nx = dp[LS]\nanswer = x * pow((1+MOD)//2,LS,MOD) % MOD\nprint(answer)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 6169845