Problem G: Get Lost

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行に出力せよ。

制約

• 入力は全て整数である
• $2 \leq w, h \leq 10^{5}(= 100000)$
• $0 \leq n \leq 10^{5}(= 100000)$
• $1 \leq g_{x}, x_{i} \leq w$
• $1 \leq g_{y}, y_{i} \leq h$
• $(x_{i}, y_{i}) \not = (g_{x}, g_{y}) (1 \leq i \leq n)$
• $(x_{i}, y_{i}) \not = (x_{j}, y_{j}) (i \not = j)$
• $r_{i} \in \{ L, R \} (1 \leq i \leq m)$
• $1 \leq m \leq 20$

入出力例

入力1

3 3 3 2 2
1 1
2 2
RL

出力1

9

以下の5通りの歩行に加え、 目的座標を開始座標とする歩行（4通り）が目的座標を通過する。

入力2

4 4 3 1 4
1 1
3 2
1 3
4 3
RR

出力2

13

以下の開始座標・進行方向から開始する歩行は目的座標を通過する。

入力3

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

出力3

647505