유괴

어느 맑은 날, X는 Y를 유괴했다. X는 Y의 눈을 가리고 차에 태워, 유괴 현장에서 X의 집까지 Y를 데리고 시내를 이동했다.

다행히 경찰의 노력으로 X는 붙잡혔고, 이 사건은 무사히 해결되었다. 그러나 X의 범행 동기만은 여전히 수수께끼로 남았다.

탐정인 당신은 범인 X의 범행 동기에 큰 관심을 가지고 여러 조사를 해 왔다. 그러던 중, 당신은 X의 "유괴 현장에서 집까지의 이동 경로"가 몇 가지나 가능한지 조사해야 할 상황에 놓였다.

범인 X가 Y를 데리고 달린 시내는 남북으로 W + 1개, 동서로 H + 1개의 도로가 지나는 바둑판 모양의 도시이며, 유괴 현장은 남서쪽 모퉁이의 교차로에, X의 집은 북동쪽 모퉁이의 교차로에 있다. 또한 Y의 증언으로 X가 좌회전과 우회전을 어떤 순서로 몇 번 했는지 알 수 있다. 게다가 범인 X는 이동 중에 같은 교차로나 도로를 두 번 이상 지났을 수도 있고, 집 앞에 와서도 멈추지 않고 그냥 지나갔을 수도 있다. 다만 범인 X는 유턴은 한 번도 하지 않았다.

예를 들어 (W, H) = (4, 3)일 때 시내는 아래 그림과 같으며, 범인 X가 굵은 선의 경로로 이동했다면 Y의 증언은 "좌회전, 우회전, 우회전, 우회전, 좌회전, 좌회전, 좌회전"이 된다.

범인 X의 이동 경로로 생각할 수 있는 경우의 수를 10 000 000(= 10^7)으로 나눈 나머지를 구하는 프로그램을 작성하라.

입력의 첫째 줄에는 두 정수 W, H (1 ≤ W, H ≤ 1000)가 쓰여 있다. 이는 남북, 동서로 지나는 도로의 수가 각각 W + 1개, H + 1개임을 나타낸다.

둘째 줄에는 정수 N (1 ≤ N ≤ 10 000)이 쓰여 있다. 이는 Y의 증언의 길이를 나타낸다.

셋째 줄에는 각 문자가 L 또는 R인, 길이 N의 문자열이 주어진다. i번째 문자가 L이면 i번째에 X가 좌회전했음을 나타내고, R이면 i번째에 X가 우회전했음을 나타낸다.

출력은 표준 출력으로 한다. 이동 경로의 경우의 수를 10 000 000(= 10^7)으로 나눈 나머지를 나타내는 정수 하나를 출력하라.