24130번 - 誘拐 (Abduction) 다국어

ある晴天の日のこと．X は Y を誘拐した．X は Y に目隠しをして，車に乗せ，誘拐現場から X の自宅まで Y を連れて市街地を移動した．

幸い，警察たちの尽力により，X は囚われの身となり，この事件はめでたく解決した．しか し，X の犯行の動機だけは謎のままとなった．

探偵であるあなたは，犯人 X の犯行動機に強い関心を持っていて，さまざまな調査を行って いた．そんな中，あなたは，X の「誘拐現場から自宅までの移動経路」が何通り考えられるか， ということを調べる必要に迫られた．

犯人 X が Y を連れて走った市街地は，南北に W + 1 本，東西に H + 1 本の道路が走る碁盤 目状の街であり，誘拐現場は南西隅の曲がり角に，X の自宅は北東隅の曲がり角に位置してい る．また，Y の証言によって，X が左折，右折をどのような順番で何回行ったかが分かってい る．さらに，犯人 X は，移動中に同じ交差点や道を二度以上通っている可能性もあるし，自宅 の前に来ても止まらずに通過したかもしれない．ただし犯人 X は，U ターンは一度も行ってい ないものとする．

たとえば，(W, H) = (4, 3) とするとき，市街地は下図のようになるが，犯人 X が太線の経路 で移動した場合，Y の証言は「左折，右折，右折，右折，左折，左折，左折」となる．

犯人 X の移動経路として考えられる場合の数を 10 000 000(= 10⁷) で割った余りを求めるプ ログラムを書け．

入力の 1 行目には 2 つの整数 W, H (1 ≤ W, H ≤ 1000) が書 かれている．これは，南北，東西に走る道路の本数がそれぞれ W + 1 本，H + 1 本であること を表す．

2 行目には，1 つの整数 N(1 ≤ N ≤ 10 000) が書かれている．これは，Y の証言の長さを表す．

3 行目には，各文字が L または R である，長さ N の文字列が与えられる．i 文字目が L であ る場合，i 回目に X が左折したことを表し，また R である場合は，i 回目に X が右折したことを 表す．

出力は，標準出力に行うこと．移動経路の場合の数を 10 000 000(= 10⁷) で割った 余りを表す 1 つの整数を出力せよ．