P28302 [洛谷] [AHOI2016 Junior Group] Black and White Sequence
提高+
题目描述

Problem Background

Xiaoke knows what kind of black and white sequences Xiaoxue likes.

Problem Description

Firstly, for any positive integer $n$, if a black and white sequence consists of $n$ consecutive black followed by $n$ consecutive white, it is definitely a sequence that Xiaoxue likes.

Secondly, if Xiaoxue likes two black and white sequences, then the new sequence formed by concatenating these two sequences together, Xiaoxue will also like. Xiaoxue does not like any other black and white sequences.

For example, if we use the characters B and W to represent black and white respectively, then sequences like BW, BBWW, BBBWWW, BWBW, BWBBWW, BWBBWWBW are all sequences that Xiaoxue likes. However, sequences like W, WW, WB, WBBW, and BBBWW are not sequences that Xiaoxue likes.

Now, Xiaoke has prepared an unfinished black and white sequence, represented by B for black, W for white, and ? for undecided positions. He wants to know how many different ways there are to determine the color for each ? position to obtain a sequence that Xiaoxue likes.

Two schemes are considered different if they differ in at least one position, and positions that are not ? are not allowed to be modified.

The answer should be taken modulo $10^9 + 9$ (a prime number).

Input Format

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

Output Format

Output an integer representing the answer.

Sample Input and Output

Sample Input #1

B?B?????

Sample Output #1

6

Sample Input #2

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

Sample Output #2

26

Sample Input #3

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

Sample Output #3

10058904

Notes

Sample Input and Output 1 Explanation

There are six valid schemes, resulting in the following final black and white sequences:

  • BBBBWWWW,
  • BBBWWWBW,
  • BWBBBWWW,
  • BWBBWWBW,
  • BWBWBBWW,
  • BWBWBWBW.

Data Size and Constraints

  • For $20\%$ of the data, the input length does not exceed $22$.
  • For $60\%$ of the data, the input length does not exceed $5000$.
  • For $100\%$ of the data, the input length does not exceed $500000$, and the sequence contains only W, B, and ? characters, where ? is an English character.
输入格式

见题面 Input 部分

输出格式

见题面 Output 部分

样例输入
B?B?????
样例输出
6