WolfDelaymasterHard | Topcoder Archive

Problem Statement

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&lt;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&lt;olen;i++){
	s[x] = 'o';				// Rewrite the x-th (0-based) character of s
	x = (x * omul + oadd) % N;
}

Definition

Class:: WolfDelaymasterHard
Method:: countWords
Parameters:: int, int, int, int, int, int, int, int, int
Returns:: int
Method signature:: int countWords(int N, int wlen, int w0, int wmul, int wadd, int olen, int o0, int omul, int oadd)
(be sure your method is public)

Constraints

N will be an even number between 2 and 2,000,000, inclusive.
wlen and olen will be between 0 and N, inclusive.
w0, wmul, wadd, o0, omul, and oadd will be between 0 and N - 1, inclusive.

Examples

```
8
```
```
5
```
```
2
```
```
3
```
```
2
```
```
0
```
```
6
```
```
7
```
```
1
```
```
Returns: 6
```
s is "w?w?????". He can obtain six valid words: "wwwwoooo", "wwwooowo", "wowwwooo", "wowwoowo", "wowowwoo", and "wowowowo".
```
20
```
```
19
```
```
12
```
```
9
```
```
15
```
```
1
```
```
8
```
```
11
```
```
1
```
```
Returns: 26
```
s is "??ww????o???ww??????".
```
40
```
```
24
```
```
34
```
```
5
```
```
11
```
```
33
```
```
35
```
```
23
```
```
27
```
```
Returns: 296
```
s is "?w?o??w????w????o????w????w????wo?wow???".
```
60
```
```
35
```
```
8
```
```
55
```
```
3
```
```
11
```
```
20
```
```
9
```
```
29
```
```
Returns: 10058904
```
s is "????????w???????????o??w?????o????????????????????o????????o".

Returns: 532199331

Returns: 861766906

```
8
```
```
6
```
```
0
```
```
1
```
```
1
```
```
3
```
```
3
```
```
6
```
```
1
```
```
Returns: 0
```
s is "wwwoww??". He can't obtain any valid words.

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.