Xiaoxue's Black-White Sequence

For any positive integer \(n\), a black-white sequence formed by concatenating \(n\) consecutive blacks (denoted by B) followed by \(n\) consecutive whites (denoted by W) is one that Xiaoxue likes.

Moreover, if Xiaoxue likes two black-white sequences, then their concatenation is also a sequence she likes. Xiaoxue does not like any other black-white sequences.

In other words, the set of sequences Xiaoxue likes is exactly those sequences that can be partitioned into one or more segments, each of which is of the form \[ B^nW^n \quad (n \ge 1), \] where each B^n represents \(n\) consecutive B characters and W^n represents \(n\) consecutive W characters.

For example, the sequences BW, BBWW, BBBWWW, as well as BWBW, BWBBWW, BWBBWWBW are liked by Xiaoxue. In contrast, sequences such as W, WW, WB, WBBW and BBBWW are not liked.

You are given an incomplete black-white sequence consisting of characters B, W, and ?. The character ? denotes an undetermined position which can be replaced by either B or W.

Your task is to determine in how many different ways you can fill each ? such that the final sequence becomes one that Xiaoxue likes. Two ways are considered different if there is at least one ? position where the replacement differs. (The positions with fixed characters must not be changed.)

Output the number of valid ways modulo \(10^9+9\) (a prime number).

inputFormat

The input consists of a single line containing a non-empty string. The string is made up of characters B, W, and ? only.

outputFormat

Output a single integer, the number of ways to replace each ? with B or W so that the final sequence is a concatenation of one or more segments of the form \(B^nW^n\) (for some \(n\ge1\)). The answer should be modulo \(10^9+9\).

sample

BW

1