你有一个$1$到$n$的排列$p_1, p_2, \dots, p_n$，对于所有的$i (1\leq i\leq n-1)$，如果$p_i$和$p_{i+1}$中，有一个数是另一个的两倍，那么会在这两个数之间画上一个点，否则不会。
现在你把所有数字都擦掉了，只剩下了这些点，请问有多少种$1$到$n$的排列满足条件。
第一行一个正整数$n (2\leq n\leq 40)$。
接下来一行一个长度为$n-1$的$01$串，其中第$i$个字符为$1$表示第$i$个数与第$i+1$个数之间有点，否则没有。
输出一个答案，由于答案可能很大，对$10^9+7$取模。
4 100
6
Comet OJ