ICPC World Finals 5日目
ティー氏はR国の街で迷ってしまった。 困ったことに、街並みが似ているため、自分が今どこにいるかが全く分からない。 R国は「おそろしあ」であるから、敵に襲撃される前にホテルへ戻らねばならない。 幸い、どのように曲がって来たかだけは覚えているので、 行き当たりばったりに進んでみよう。
\( w \times h \)マスの二次元格子状のマップがある。 左上のマスの座標を\( (1, 1) \)、右下のマスの座標を\( (w, h) \)とする。 マップの周りは壁で囲まれており、 \(n\)個の障害物が座標\( (x_{i}, y_{i}) (1 \leq i \leq n) \)に置かれている。 さらに、命令列\( r_{1}r_{2} \cdots r_{m} \)と目的座標\( (g_{x}, g_{y}) \)が与えられる。 開始座標と進行方向の設定後、歩行者は以下の移動規則に従って歩行を開始する。
1. カウンタを\( i=1
\)に初期化し、開始座標と進行方向（上・下・左・右）を設定する。
2. 壁・障害物に出会うまで直進する。
3. 壁・障害物の手前で次のいずれかを実行する。
3. a. \( i>m \)、すなわち命令が無ければ歩行を終了する。
3. b. 命令\( r_{i} \)がLならば左、Rならば右へ方向転換する。
4. \( i \)をインクリメントする。
5. 2.に戻る。
歩行開始から歩行終了までに通過した座標（開始座標を含む）に目的座標\( (g_{x}, g_{y}) \)が含まれれば、歩行者が目的地に辿り着いたと解釈する。 目的地に辿り着くことのできる開始座標・進行方向の組み合わせは何通りあるかを求めよ。 ただし、開始座標には障害物やマップ外の座標を設定することはできないとする。 （目的座標を設定することはできる。）
w h gx gy n x1 y1 … xn yn r1r2 … rm
1行目に マップの横幅\(w\)、縦幅\(h\)、目的地のx座標\( g_{x} \)、目的地のy座標\( g_{y} \)、障害物の数\(n\)が空白区切りで与えられる。 2行目から\( n+1 \)行目に 各障害物の座標\( (x_{i}, y_{i}) \)が空白区切りで与えられる。 \( n+2 \)行目に長さ\(m\)の命令列\( r_{1}r_{2} \cdots r_{m} \)が与えられる。
目的地に辿り着けるような 開始座標・進行方向の組み合わせの数を1行に出力せよ。
3 3 3 2 2 1 1 2 2 RL
9
以下の5通りの歩行に加え、 目的座標を開始座標とする歩行（4通り）が目的座標を通過する。
4 4 3 1 4 1 1 3 2 1 3 4 3 RR
13
以下の開始座標・進行方向から開始する歩行は目的座標を通過する。
100000 100000 46597 49716 17 38713 77141 46598 78075 66177 49715 58569 77142 48303 12742 32829 65105 32830 78076 70273 27408 48302 21196 27119 54458 38714 65104 46598 54457 27118 12743 60242 21197 60241 1101 58568 27409 93581 1100 LLRRLLLLRRLL
647505