##### 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.

*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.

*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:

*Figure 3.*)

We let the letter `A`

represent light colored balls and the letter `B`

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
are `UUD`

, `UDU`

, and `DUU`

. Finally, the corresponding output sequences
produced are (from left to right) respectively `BAB`

, `BBA`

, and `BBA`

.
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.

#### Input Specification

The first line contains two integers and , respectively
representing the number of marbles in the upper and lower pipes on the
left side.

The second line contains a string of `A`

's and `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
marble.

The third line contains a string of `A`

's and `B`

's of length ,
describing the marbles in the lower left side pipe.

#### Output Specification

The output should consist of a single line with a single integer, modulo .

#### Sample Input

```
2 1
AB
B
```

#### Sample Output

`5`

#### Explanation

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.

#### Constraints

About 30% of the test cases will satisfy .

About 100% of the test cases will satisfy .

## Comments