Description

派大星新买了一个键盘。

但是这个键盘太硬核了，只有三个按键。

• 按下 1：输入一个 1 接在当前屏幕上的字符串的后面。

• 按下 0：输入一个 0 接在当前屏幕上的字符串的后面。

• 按下 backspace：如果当前屏幕上为空串，则什么都不会发生，否则删除最后的一个字符。

派大星现在想输入一个字符串 $S$ 。

派大星想知道按不超过 $N$ 下按键，有多少种方案最后屏幕上的字符串为字符串 $S$。（对 $10^9 + 7$ 取模）

Input Format

从文件 keyboard.in 读入数据。

n

S

Output Format

向文件 keyboard.out 输出数据。

输出满足条件输入方案的数量 $mod 10^9 + 7$。

Sample

样例输入1

3
01

样例输出1

2

样例输入2

3
0

样例输出2

7

Hint

| part | $n$ | $S$ |

| ------ | ------------------ | -------------------- |

| $20\%$ | $1 \le n \le 20$ | |

| $50\%$ | $1 \le n \le 300$ | |

| $all$ | $1 \le n \le 5000$ | $1 \le len(S) \le 5000$ |