National Olympiad in Informatics, China, 2009
Pipe Marbles is one of little X's favorite games. In this question, we shall consider a simple version of it. A screen of the game is depicted below in figure 1.
At the start of the game, the upper and lower pipes on the left side each contain a fixed amount of marbles (some are dark colored and some are light colored), and the output pipe on the right side is empty. In each move, one can select a pipe from the left side and move the rightmost marble from that pipe to the right output pipe.
For instance, we can move a marble from the lower left pipe into the output pipe, as depicted below in figure 2.
Assuming there are marbles in the upper and marbles in the lower pipe, then completing the game will require moves to move all of the marbles from the left pipe to the output pipe. At the end, the marbles in the output pipe from left to right will form an output sequence.
As a math fanatic, little X knows that he has a total of different ways to complete the game, where different ways can produce the same output sequence. For example, consider the game scenario depicted below in figure 3:
We let the letter
A represent light colored balls and the letter
represent dark colored balls. Denote the action of moving a ball from
the upper pipe to the right pipe as
U, and the action of moving a ball
from the lower pipe to the right pipe as
D, then there are a total of
different ways to complete the game. Respectively, they
DUU. Finally, the corresponding output sequences
produced are (from left to right) respectively
The latter two ways therefore produce the same output sequence.
Assuming that it's possible to create different types of final output sequences, and that there are ways (i.e. the number of different sequence of moves) to create the -th type of these output sequences. Little X has known for a long time that:
Thus, little X wishes to compute the value of:
Can you help him determine this value? Since it may be very large, you are only required to output it modulo (the remainder when divided by ).
Note: The aforementioned represents a combination. equals the number of ways to choose items from a collection of different items.
The first line contains two integers and , respectively
representing the number of marbles in the upper and lower pipes on the
The second line contains a string of
B's of length ,
describing the marbles in the upper left side pipe from left to right.
A represents a light colored marble and
B represents a dark colored
The third line contains a string of
B's of length ,
describing the marbles in the lower left side pipe.
The output should consist of a single line with a single integer, modulo .
2 1 AB B
The sample follows the example in figure 3, where there are two possible
distinct output sequences. The sequence
BAB has 1 way of being
created, and the sequence
BBA has 2 ways of being created. Therefore,
the answer is 5.
About 30% of the test cases will satisfy .
About 100% of the test cases will satisfy .