Alice and Bob are playing a game consisting of $n$ rounds. You are given a string s of length $n$, where each character s[i] represents the creature Alice summons in the $i^{ ext{th}}$ round:

• 'F' represents a Fire Dragon

• 'W' represents a Water Serpent

• 'E' represents an Earth Golem

In each round, Bob also summons one of these three creatures. The outcome of each round is determined as follows:

• Fire Dragon beats Earth Golem ('F' beats 'E').

• Water Serpent beats Fire Dragon ('W' beats 'F').

• Earth Golem beats Water Serpent ('E' beats 'W').

In every round:

• If Bob summons a creature that beats Alice’s creature, Bob receives $1$ point.

• If Alice’s creature beats Bob’s creature, Bob loses $1$ point.

• If both summon the same creature, neither receives points ($0$ points).

Bob must follow a strict constraint: he cannot summon the same creature in two consecutive rounds.

Bob wins the game if his total points at the end of all $n$ rounds are strictly greater than $0$.

Return the number of distinct winning move sequences Bob can make. Since the answer can be large, return it modulo $10^9 + 7$.

Constraints:

• $1 \leq$ s.length $\leq 1000$

• s[i] is one of 'F', 'W', or 'E'.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.