"Ball Pipeline" is a game that Little X really likes. In this problem, we consider a simplified version of this game. The game screen is shown in Figure 1:

(Figure 1)

At the beginning of the game, the two pipes on the left (upper and lower) each contain a certain number of balls (of two types: dark and light), while the output pipe on the right is empty. In each operation, you can choose one of the pipes on the left and push the rightmost ball from that pipe into the output pipe on the right.

For example, if we first move one ball from the lower pipe to the output pipe, we get the situation shown in Figure 2.

(Figure 2)

Suppose there are $n$ balls in the upper pipe and $m$ balls in the lower pipe. The entire game process requires $n + m$ operations, which means moving all the balls from the left pipes into the output pipe. The final $n + m$ balls form an output sequence from right to left in the output pipe.

Little X, who loves mathematics, knows that there are a total of $C(n+m, n)$ different ways to perform the operations, and different operation sequences may lead to the same output sequence. For example, for the game situation shown in Figure 3:

(Figure 3)

We use A to represent a light-colored ball and B to represent a dark-colored ball. Let U be the operation of moving the rightmost ball from the upper pipe, and D be the operation of moving the rightmost ball from the lower pipe. There are $C(2+1, 1) = 3$ different operation sequences, which are UUD, UDU, and DUU. The final output sequences formed in the output pipe (from right to left) are BAB, BBA, and BBA, respectively. It can be seen that the latter two operation sequences result in the same output sequence.

Suppose there are $K$ different types of output sequences that can be produced, and the $i$-th output sequence can be produced in $a_i$ ways (i.e., the number of different operation sequences). The clever Little X already knows that:

$$\sum_{i=1}^{k} a_i = C(n+m, n)$$

Therefore, Little X wants to calculate:

$$\sum_{i=1}^{k} a_i^2$$

Can you help him calculate this value? Since this value can be very large, you only need to output the value modulo 1024523 (i.e., the remainder when divided by 1024523).

Note: $C(n+m, n)$ denotes the binomial coefficient. The binomial coefficient $C(a, b)$ is equivalent to the number of ways to choose $b$ items from $a$ distinct items.

Input

The first line contains two integers $n$ and $m$, representing the number of balls in the upper and lower pipes, respectively.

The second line is an AB string of length $n$, representing the types of balls in the upper pipe from left to right. A represents a light-colored ball, and B represents a dark-colored ball.

The third line is an AB string of length $m$, representing the situation in the lower pipe.

Output

The output contains only one line, which is the value of $\sum_{i=1}^{k} a_i^2$ modulo 1024523.

Examples

Input 1

2 1
AB
B

Output 1

5

Note

The example is the one shown in (Figure 3) in the text. There are two different types of output sequences: the sequence BAB has 1 way to be produced, and the sequence BBA has 2 ways to be produced, so the answer is 5.

Constraints

Approximately 30% of the data satisfies $n, m \le 12$; Approximately 100% of the data satisfies $n, m \le 500$.