黑白序列

黑白序列

测试数据来自 system/1990

描述

小可可知道小雪喜欢什么样子的黑白序列。

首先,对于任何正整数n,如果一个黑白序列是由连续n个黑接上连续n个白,那一定是小雪喜欢的黑白序列。

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

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

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

例如,对于B?B?????来说,有六种合法方案,依次得到的最终黑白序列为:BBBBWWWW,BBBWWWBW,BWBBBWWW,BWBBWWBW,BWBWBBWW与BWBWBWBW。

格式

输入格式

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

输出格式

输出一个整数,表示一共有多少种不同的方案,两个方案若有至少一位不同才能算是不同的,不是问号?的位置是不允许修改的。最终答案对素数1000000009取余。

样例1

样例输入1

B?B?????

样例输出1

6

样例2

样例输入2

??BB????W???BB??????

样例输出2

26

样例3

样例输入3

????????B???????????W??B?????W????????????????????W????????W

样例输出3

10058904

限制

对于20%的数据,输入长度不超过22。
对于60%的数据,输入长度不超过5000。
对于100%的数据,输入长度不超过500000。

信息

ID
2021
难度
(无)
分类
(无)
标签
(无)
递交数
0
已通过
0
通过率
?
上传者