The card game War is usually played with 52 cards.
Alice and Bob enjoy the game so much that they have modified it to use N cards, and they have changed the rules significantly.
The rules of their game are as follows:
The cards are numbered from 0 to N-1.
At the beginning of the game, each of the N cards is assigned to either Alice or Bob with equal probability.
The choices are made independently of each other and there is no guarantee that the players will receive the same number of cards.
The game consists of a series of steps.
In each step, a pair of cards is selected uniformly at random from all possible pairs that consist of two distinct cards.
The owner of the lower-numbered card becomes the owner of both cards in the pair.
(If that player already owned both cards, nothing changes, but it still counts as a step.)
The game ends as soon as all cards are owned by the same player.
Note that the game can end without any steps if all cards are initially assigned to the same player.
Carol watches Alice and Bob play the game.
She likes peas, so she has invented the following rules for herself:
Before the beginning of the game Carol chooses a specific state, i.e., a specific way cards are distributed between Alice and Bob.
At the beginning of the game and also after each step, if the current state is Carol's chosen state, she eats a pea.
You are given Carol's chosen state as a String **state**.
For each valid i, **state**[i] is either 'A' or 'B', indicating whether card i is owned by Alice or Bob.
We are interested in the expected number of peas Carol will eat during a game.
This number can always be written as p / q, where p and q are positive coprime integers.
Let X be an integer such that X * q is congruent to p, modulo 1,000,000,007.
Return the value (X mod 1,000,000,007). |