Problem Statement
给定一个由'w','o','?'三种字符组成的字符串 s ，
问有多少种方案将'?'变为'w'或'o'，
使得新字符串为若干个长度为偶数且前一半全部为'w'，
后一半全部为'o'的字符串连接形成。答案对10^9+7取模。
s的长度：2000001
Wolf Sothe is playing the game Delaymaster.
In this game, he can create new words according to the following rules:
- For each positive integer n, the string which consists of n copies of 'w' followed by n copies of 'o' is a valid word.
- The concatenation of two valid words is a valid word.
- Only the words that can be obtained by rules 1 and 2 are valid. There are no other valid words.
Thus, for example:
- By rule 1, "wo", "wwoo", and "wwwwwooooo" are valid words.
- Then, by rule 2, "wowwoo" is a valid word.
- By applying rule 2 twice, "wowwoowo" is a valid word.
- The strings "w", "ow", "woow", and "wwwoo" are not valid words.
Sothe has a very long string s.
Each character of s is one of 'w', 'o', and '?'.
Sothe wants to replace each '?' with either 'w' or 'o' in such a way that the result is a valid word.
Return the number of different valid words he can obtain this way, modulo 1,000,000,007.
As s can be very long, you will have to generate it in your program.
You are given nine ints: N, wlen, w0, wmul, wadd, olen, o0, omul, and oadd.
Use the following pseudocode to generate s:
s = "???...???"; // Concatenation of N '?'s
signed_64bit_integer x = w0;
for(i=0;i<wlen;i++){
s[x] = 'w'; // Rewrite the x-th (0-based) character of s
x = (x * wmul + wadd) % N;
}
x = o0;
for(i=0;i<olen;i++){
s[x] = 'o'; // Rewrite the x-th (0-based) character of s
x = (x * omul + oadd) % N;
}