파이프 구슬

Pipe Marbles는 어린 X가 가장 좋아하는 게임 중 하나이다. 이 문제에서는 이 게임의 간단한 버전을 생각한다. 게임 화면은 아래 그림 1에 나와 있다.

(그림 1.)

게임이 시작될 때 왼쪽의 위쪽 파이프와 아래쪽 파이프에는 각각 정해진 수의 구슬이 들어 있고(일부는 어두운 색, 일부는 밝은 색), 오른쪽의 출력 파이프는 비어 있다. 각 이동에서는 왼쪽의 파이프 하나를 골라 그 파이프의 가장 오른쪽 구슬을 오른쪽 출력 파이프로 옮긴다.

예를 들어, 아래 그림 2처럼 왼쪽 아래 파이프에서 구슬을 출력 파이프로 옮길 수 있다.

(그림 2.)

위쪽 파이프에 n개, 아래쪽 파이프에 m개의 구슬이 있다고 하면, 게임을 끝내려면 왼쪽 파이프의 모든 구슬을 출력 파이프로 옮기는 n + m번의 이동이 필요하다. 마지막에 출력 파이프에 있는 n + m개의 구슬이 왼쪽에서 오른쪽으로 이루는 수열을 출력 수열이라고 한다.

수학을 좋아하는 어린 X는 게임을 끝내는 방법이 모두 C(n + m, n)가지라는 것을 알고 있다. 서로 다른 방법이 같은 출력 수열을 만들 수도 있다. 예를 들어 아래 그림 3의 게임 상황을 보자.

(그림 3.)

밝은 색 공을 문자 A, 어두운 색 공을 문자 B로 나타내자. 위쪽 파이프에서 공을 오른쪽 파이프로 옮기는 행동을 U, 아래쪽 파이프에서 공을 오른쪽 파이프로 옮기는 행동을 D라고 하면, 게임을 끝내는 방법은 모두 C(2+1, 1) = 3가지이다. 각각 UUD, UDU, DUU이다. 마지막에 만들어지는 출력 수열은 왼쪽에서 오른쪽으로 각각 BAB, BBA, BBA이다. 따라서 뒤의 두 방법은 같은 출력 수열을 만든다.

최종 출력 수열이 K가지 종류라고 하고, 이 출력 수열들 중 i번째 종류를 만드는 방법의 수(즉, 서로 다른 이동 수열의 개수)가 ai라고 하자. 어린 X는 오래전부터 다음을 알고 있었다.

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

그래서 어린 X는 다음 값을 계산하려고 한다.

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

이 값을 구할 수 있겠는가? 값이 매우 클 수 있으므로 1024523으로 나눈 나머지만 출력하면 된다.

참고: 앞에서 말한 C(n + m, n)은 조합을 나타낸다. C(a, b)는 서로 다른 a개 중에서 b개를 고르는 방법의 수이다.

첫째 줄에는 두 정수 n과 m이 주어진다. 각각 왼쪽의 위쪽 파이프와 아래쪽 파이프에 있는 구슬의 개수이다.

둘째 줄에는 길이 n의 A와 B로 이루어진 문자열이 주어진다. 왼쪽 위쪽 파이프의 구슬을 왼쪽에서 오른쪽으로 나타낸다. A는 밝은 색 구슬, B는 어두운 색 구슬이다.

셋째 줄에는 길이 m의 A와 B로 이루어진 문자열이 주어진다. 왼쪽 아래쪽 파이프의 구슬을 나타낸다.

구하려는 값을 1024523으로 나눈 나머지를 한 줄에 출력한다.

n, m ≤ 500