3790: 跳棋(第二轮04)
题目描述
白浅妹妹喜欢玩跳棋， 她定义唯一合法的跳法是一个棋子 x 跳过一个相邻的棋子 y 到该直线上与 y 相邻的空位。 她试图给一个局面能达到的所有局面计数。 为了让大家都 能做出这道题，所以白浅妹妹给出的是一个 1 × n 的棋盘。 白浅妹妹会告诉你初始每个 位置是否有棋子，或者她觉得这个位置无所谓有没有棋子。 你需要对于每一种棋盘的可能 的初始情况，求出这个局面经过若干步跳跃能达到的局面有多少种。 为了减少输出量，你 只需要输出每种可能初始情况对应答案之和对 109 + 7取模的结果。
加油啊，热爱测样例的大哥哥：sample.zip
输入
第一行包含一个正整数 x，表示棋盘的大小为 1 × n 。 第二行包含 n 个字符， 0 表示空 位， 1 表示棋子， ? 表示无所谓，可以是棋子也可以是空位。
输出
输出一行一个整数表示答案。
样例输入 复制
5
?0110样例输出 复制
7提示
【样例 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)：n ≤ 10
subtask2 (10pts)：n ≤ 20, ‘? ’的个数小于等于 5。
subtask3 (20pts)：n ≤ 500，保证序列中全部为 ‘? ’。
subtask4 (20pts)：n ≤ 500, 保证序列中不存在‘? ’，且只存在一段连续的棋子。
subtask5 (40pts)：n ≤ 500 。 对于 100% 的数据， n ≤ 500。