← 返回题目
题库练习 [AHOI2016初中组] 黑白序列
← 上一题 下一题 →

A2820 | [AHOI2016初中组] 黑白序列

来源2016
时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

小可可知道小雪喜欢什么样子的黑白序列。首先，对于任何正整数 $n$，如果一个黑白序列是由连续 $n$ 个黑接上连续 $n$ 个白，那一定是小雪喜欢的黑白序列。

其次，如果有两个黑白序列小雪都喜欢，那么把这两个序列接起来得到的新序列，小雪也一定喜欢。小雪不会喜欢更多别的黑白序列。

例如，如果用字符 B 和 W 分别表示黑色，W 表示白色，那么 BW，BBWW，BBBWWW 以及 BWBW，BWBBWW，BWBBWWBW 都是小雪喜欢的黑白序列。而 W，WW，WB，WBBW 以及 BBBWW 都不是小雪喜欢的黑白序列。

现在小可可准备了一个未完成的黑白序列，用 B 和 W 表示黑色和白色，用 ? 表示尚未确定，他希望知道一共有多少种不同的方法，在决定了每一个 ? 位置的颜色后可以得到一个小雪喜欢的黑白序列。

两个方案若有至少一位不同才能算是不同的，不是 ? 的位置是不允许修改的。

答案对 $10^9 + 9$（一个素数）取模。

输入格式

第一行输入一个长度大于零的字符串，由 B，W 和 ? 组成。

输出格式

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

输入输出样例

输入 #1
B?B?????
输出 #1
6
输入 #2
??BB????W???BB??????
输出 #2
26
输入 #3
????????B???????????W??B?????W????????????????????W????????W
输出 #3
10058904
C++ 编辑器
输入
输出