题目描述

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

B?B?????

输出样例#1：

6

输入样例#2：

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

输出样例#2：

26

输入样例#3：

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

输出样例#3：

10058904

数据说明：

 对于 20% 的数据，输入长度不超过 22。
对于 60% 的数据，输入长度不超过 5000。
对于 100% 的数据，输入长度不超过 500000，保证序列中只含 W，B，? 三种字符，其中 ? 是英文字符。