### National Olympiad in Informatics, China, 2009

## Day 2, Problem 2 - Pipe Marbles

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 `n` marbles in the upper and `m` marbles in the lower pipe, then completing the game will require `n` + `m` moves to move all of the marbles from the left pipe to the output pipe. At the end, the `n` + `m` 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 `C`(`n` + `m`, `n`) 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 `C`(2+1, 1) = 3 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 `K` different types of final output sequences, and that there are `a _{i}` ways (i.e. the number of different sequence of moves) to create the

`i`-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 1024523 (the remainder when divided by 1024523).

**Note:** The aforementioned `C`(`n` + `m`, `n`) represents a combination. `C`(`a`, `b`) equals the number of ways to choose `b` items from a collection of `a` different items.

### Input Format

The first line contains two integers `n` and `m`, 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 `n`, 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 `m`, describing the marbles in the lower left side pipe.

### Output Format

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

### 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 `n`, `m` ≤ 12.

About 100% of the test cases will satisfy `n`, `m` ≤ 500.

All Submissions

Best Solutions

**Point Value:** 17 (partial)

**Time Limit:** 2.00s

**Memory Limit:** 512M

**Added:** Aug 04, 2014

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...