Count The Number of Winning Sequences
international master · 1930 · lc hard +32 · 32.1% accepted · 104 likes · top 10%
Description
Alice and Bob play a fantasy battle game over n rounds, summoning one of three creatures each round: a Fire Dragon, a Water Serpent, or an Earth Golem. Both players reveal their choices simultaneously, and points are awarded as follows:
- A Fire Dragon defeats an Earth Golem; the Fire Dragon player earns a point.
- A Water Serpent defeats a Fire Dragon; the Water Serpent player earns a point.
- An Earth Golem defeats a Water Serpent; the Earth Golem player earns a point.
- Identical creatures yield no points for either player.
You are given a string s of length n using characters 'F', 'W', and 'E' to encode Alice's summon sequence for each round:
- s[i] == 'F' means Alice summons a Fire Dragon.
- s[i] == 'W' means Alice summons a Water Serpent.
- s[i] == 'E' means Alice summons an Earth Golem.
Bob's choices are unknown, but he is guaranteed never to pick the same creature in two consecutive rounds. Bob wins if his total points after all n rounds strictly exceed Alice's.
Return the count of distinct sequences Bob can play to beat Alice.
Since the answer may be very large, return it modulo 109 + 7.
Code