Format

Input

读入格式如下：
n
s

Output

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

Sample 1

Input

3
01

Output

2

Sample 2

Input

3
0

Output

7

Limitation

2s, 256MiB for each test case.