描述
小可可知道小雪喜欢什么样子的黑白序列。
首先，对于任何正整数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。
