Description

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).

Input Format

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

Output Format

Output a single integer, the answer.

B?B?????

6

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

26

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

10058904

Hint

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