NOI
全国青少年信息学奥林匹克联赛(NOIPOJ)在线评测系统
NOIPOJ在线评测系统
Problem63--黑白序列 [bwsque]

63: 黑白序列 [bwsque]

Time Limit: 1000 Sec  Memory Limit: 128 MB
Submit: 5  Solved: 4
[Submit] [Status] [Web Board] [Creator:]

Description

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

首先,对于任何正整数 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。

Input

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

Output

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

Sample Input Copy

B?B?????

Sample Output Copy

6

HINT

数据规模:

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

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

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

Source/Category