D. Song of Loneliness
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Laplace Computing Center is trying to crack a warlock's code.

There are three operations. Your task is to use them to type out a given 01 string $$$S$$$.

The three operations are 0, 1, and B:

  • Operation 0 means appending a 0 to the end of the current string.
  • Operation 1 means appending a 1 to the end of the current string.
  • Operation B means deleting the last character of the current string. In particular, if the current string is empty, this operation does nothing.
Initially, the string on the typewriter is empty.

You must perform exactly $$$n$$$ operations and type out the given 01 string $$$S$$$.

Find the number of operation sequences that satisfy this requirement. Print the answer modulo $$$10^9+7$$$.

Input

The first line contains an integer $$$n$$$ ($$$1\le n\le5000$$$).

The second line contains a 01 string $$$S$$$ ($$$1\le |S|\le n$$$).

Output

Output a single integer, the number of valid operation sequences modulo $$$10^9+7$$$.

Examples
Input
3
1
Output
5
Input
9
110
Output
509
Note

In the first example, there are $$$5$$$ valid operation sequences: 10B, 11B, 0B1, 1B1, BB1.