A22531.[AHOI2016初中组] 黑白序列
省选/NOI-
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
小可可知道小雪喜欢什么样子的黑白序列。首先,对于任何正整数 n,如果一个黑白序列是由连续 n 个黑接上连续 n 个白,那一定是小雪喜欢的黑白序列。
其次,如果有两个黑白序列小雪都喜欢,那么把这两个序列接起来得到的新序列,小雪也一定喜欢。小雪不会喜欢更多别的黑白序列。
例如,如果用字符 B
和 W
分别表示黑色,W
表示白色,那么 BW
,BBWW
,BBBWWW
以及 BWBW
,BWBBWW
,BWBBWWBW
都是小雪喜欢的黑白序列。而 W
,WW
,WB
,WBBW
以及 BBBWW
都不是小雪喜欢的黑白序列。
现在小可可准备了一个未完成的黑白序列,用 B
和 W
表示黑色和白色,用 ?
表示尚未确定,他希望知道一共有多少种不同的方法,在决定了每一个 ?
位置的颜色后可以得到一个小雪喜欢的黑白序列。
两个方案若有至少一位不同才能算是不同的,不是 ?
的位置是不允许修改的。
答案对 109+9(一个素数)取模。
输入格式
第一行输入一个长度大于零的字符串,由 B
,W
和 ?
组成。
输出格式
输出一个整数,表示答案。
输入输出样例
输入#1
B?B?????
输出#1
6
输入#2
??BB????W???BB??????
输出#2
26
输入#3
????????B???????????W??B?????W????????????????????W????????W
输出#3
10058904
说明/提示
样例输入输出 1 解释
有六种合法方案,依次得到的最终黑白序列为:
BBBBWWWW
,BBBWWWBW
,BWBBBWWW
,BWBBWWBW
,BWBWBBWW
,BWBWBWBW
。
数据规模与约定
- 对于 20% 的数据,输入长度不超过 22。
- 对于 60% 的数据,输入长度不超过 5000。
- 对于 100% 的数据,输入长度不超过 500000,保证序列中只含
W
,B
,?
三种字符,其中?
是英文字符。