【题目描述】

白浅妹妹喜欢玩跳棋，她定义唯一合法的跳法是一个棋子 $𝑥$ 跳过一个相邻的棋子 $𝑦$ 到该直线上与 $𝑦$ 相邻的空位。 她试图给一个局面能达到的所有局面计数。

为了让大家都能做出这道题，所以白浅妹妹给出的是一个 $1 × 𝑛$ 的棋盘。 白浅妹妹会告诉你初始每个位置是否有棋子，或者她觉得这个位置无所谓有没有棋子。 你需要对于每一种棋盘的可能的初始情况，求出这个局面经过若干步跳跃能达到的局面有多少种。

为了减少输出量，你只需要输出每种可能初始情况对应答案之和对 $10^9 + 7$ 取模的结果。

大样例：sample.zip

【输入格式】

第一行包含一个正整数 $𝑥$，表示棋盘的大小为 $1 × 𝑛$。 第二行包含 $𝑛$ 个字符，0 表示空位，1 表示棋子，? 表示无所谓，可以是棋子也可以是空位。

【输出格式】

输出一行一个整数表示答案。

【样例 1 输入】

5
?0110

【样例 1 输出】

7

【说明】

【样例 1 解释】共有两种可能的序列。对于序列 00110，有4种可能，分别是

11000, 01100, 00110, 00011。对于序列10110, 有3种可能, 分别是 11100，10110，10011。

大样例说明：

sample3.in 和 sample3.ans 满足 subtask 2

sample4.in 和 sample4.ans 满足 subtask 3

sample5.in 和 sample5.ans 满足 subtask 4

sample6.in 和 sample6.ans 满足 subtask 5

【样例 2 输入】

3
???

【样例 2 输出】

10

【说明】

三个问号本身可以产生 8 种初始局面，由初始局面 110 可以跳成 011，这是第 9 种局面；由初始局面 011 可以跳成 110，这是第 10 种局面。也就是说也许最终局面一样，但是跳出来的方式不同，则认为是不同的方案。

【备注】

• subtask1 (10pts)：$𝑛 ≤ 10$。
• subtask2 (10pts)：$𝑛 ≤ 20$, ‘?’的个数小于等于 5。
• subtask3 (20pts)：$𝑛 ≤ 500$，保证序列中全部为‘?’。
• subtask4 (20pts)：$𝑛 ≤ 500$, 保证序列中不存在‘? ’，且只存在一段连续的棋子。
• subtask5 (40pts)：$𝑛 ≤ 500$。
• 对于 100% 的数据，$𝑛 ≤ 500$。