P2779 [AHOI2016初中组] 黑白序列

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

首先，对于任何正整数 $n$，如果一个黑白序列是由连续 $n$ 个黑接上连续 $n$ 个白，那一定是小雪喜欢的黑白序列。 其次，如果有两个黑白序列小雪都喜欢，那么把这两个序列接起来得到的新序列，小雪也一定喜欢。小雪不会喜欢更多别的黑白序列。 例如，如果用字符 `B` 和 `W` 分别表示黑色，`W` 表示白色，那么 `BW`，`BBWW`，`BBBWWW` 以及 `BWBW`，`BWBBWW`，`BWBBWWBW` 都是小雪喜欢的黑白序列。而 `W`，`WW`，`WB`，`WBBW` 以及 `BBBWW` 都不是小雪喜欢的黑白序列。 现在小可可准备了一个未完成的黑白序列，用 `B` 和 `W` 表示黑色和白色，用 `?` 表示尚未确定，他希望知道一共有多少种不同的方法，在决定了每一个 `?` 位置的颜色后可以得到一个小雪喜欢的黑白序列。 两个方案若有至少一位不同才能算是不同的，不是 `?` 的位置是不允许修改的。 答案对 $10^9 + 9$（一个素数）取模。

第一行输入一个长度大于零的字符串，由 `B`，`W` 和 `?` 组成。

输出一个整数，表示答案。

#### 样例输入输出 1 解释 有六种合法方案，依次得到的最终黑白序列为： - `BBBBWWWW`， - `BBBWWWBW`， - `BWBBBWWW`， - `BWBBWWBW`， - `BWBWBBWW`， - `BWBWBWBW`。 #### 数据规模与约定 - 对于 $20\%$ 的数据，输入长度不超过 $22$。 - 对于 $60\%$ 的数据，输入长度不超过 $5000$。 - 对于 $100\%$ 的数据，输入长度不超过 $500000$，保证序列中只含 `W`，`B`，`?` 三种字符，其中 `?` 是英文字符。