You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

【题目描述】

白浅妹妹喜欢玩跳棋，她定义唯一合法的跳法是一个棋子 $𝑥$ 跳过一个相邻的棋子 $𝑦$到该直线上与 $𝑦$ 相邻的空位。 她试图给一个局面能达到的所有局面计数。 为了让大家都能做出这道题，所以白浅妹妹给出的是一个 1 × $𝑛$ 的棋盘。 白浅妹妹会告诉你初始每个位置是否有棋子，或者她觉得这个位置无所谓有没有棋子。 你需要对于每一种棋盘的可能的初始情况，求出这个局面经过若干步跳跃能达到的局面有多少种。 为了减少输出量，你只需要输出每种可能初始情况对应答案之和对 $10^9 + 7$取模的结果。

【输入格式】

第一行包含一个正整数 $x$，表示棋盘的大小为 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)：$𝑛 \le 10$

subtask2 (10pts)：$𝑛 \le 20$, ‘? ’的个数小于等于 5。

subtask3 (20pts)：$𝑛 \e 500$，保证序列中全部为‘? ’。

subtask4 (20pts)：$𝑛 \le 500$, 保证序列中不存在‘? ’，且只存在一段连续的棋子。

subtask5 (40pts)：$𝑛 \le 500$。 对于 100% 的数据，$𝑛 \le 500$。