P2779 [AHOI2016 Middle School] Black-and-White Sequence

Xiao Keke knows what kind of black-and-white sequences Xiaoxue likes.

First, for any positive integer $n$, if a black-and-white sequence consists of $n$ consecutive blacks followed by $n$ consecutive whites, then Xiaoxue definitely likes it. Second, if Xiaoxue likes two black-and-white sequences, then she also likes the new sequence obtained by concatenating these two sequences. Xiaoxue does not like any other black-and-white sequences. For example, use characters `B` and `W` to denote black and white, respectively. Then `BW`, `BBWW`, `BBBWWW`, as well as `BWBW`, `BWBBWW`, `BWBBWWBW` are sequences that Xiaoxue likes. In contrast, `W`, `WW`, `WB`, `WBBW`, and `BBBWW` are not liked by Xiaoxue. Now Xiao Keke has prepared an incomplete black-and-white sequence, where `B` and `W` denote black and white, and `?` denotes undecided. He wants to know how many different ways there are to decide the color at every `?` so that the resulting sequence is liked by Xiaoxue. Two assignments are considered different if they differ at least at one position. Positions that are not `?` are not allowed to be modified. Output the answer modulo $10^9 + 9$ (a prime).

The first line contains a non-empty string consisting of `B`, `W`, and `?`.

Output a single integer, the answer.

Explanation for Sample Input/Output 1: There are six valid assignments, and the resulting sequences are: - `BBBBWWWW`, - `BBBWWWBW`, - `BWBBBWWW`, - `BWBBWWBW`, - `BWBWBBWW`, - `BWBWBWBW`. Constraints: - For 20% of the testdata, the input length does not exceed 22. - For 60% of the testdata, the input length does not exceed 5000. - For 100% of the testdata, the input length does not exceed 500000. The sequence contains only the three characters `W`, `B`, and `?`, where `?` is the ASCII question mark. Translated by ChatGPT 5