Abduction(誘拐) - joi2009-day2

時間制限: 1秒

メモリ制限: 64MB

ある晴天の日のこと, 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^7) で割った余りを求めるプログラムを書け.

Input.

入力ファイルabduction.inの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が右折したことを表す.

Output.

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

採点基準

採点用データのうち, 配点の40% 分については, W,H ≤ 40 を満たす.

例1

abduction.in	標準出力
`4 3 7 LRRRLLL`	`80`

例2

abduction.in	標準出力
`4 4 3 RLR`	`9`