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:
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$$$.
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 a single integer, the number of valid operation sequences modulo $$$10^9+7$$$.
31
5
9110
509
In the first example, there are $$$5$$$ valid operation sequences: 10B, 11B, 0B1, 1B1, BB1.