AT_abc341_c [ABC341C] Takahashi Gets Lost

[problemUrl]: https://atcoder.jp/contests/abc341/tasks/abc341_c $ H $ 行 $ W $ 列のグリッドがあります。 グリッドの各マスは**陸**か**海**のどちらかであり、 その情報は $ H $ 個の長さ $ W $ の文字列 $ S_1,\ S_2,\ \ldots,\ S_H $ で与えられます。 上から $ i $ 行目、左から $ j $ 列目のマスを $ (i,\ j) $ で表すと、 $ S_i $ の $ j $ 文字目が `.` のときマス $ (i,\ j) $ は陸であり、`#` のときマス $ (i,\ j) $ は海です。 ここで、グリッドの外周のマス（すなわち、$ i\ =\ 1 $ 、$ i\ =\ H $ 、$ j\ =\ 1 $ 、$ j\ =\ W $ のうち少なくとも $ 1 $ 個以上を満たすマス $ (i,\ j) $ ）については、すべて海であることが制約として保証されます。 高橋君が乗った宇宙船が、グリッド上のあるマスに不時着してしまいました。 その後、高橋君は `L` 、`R` 、`U` 、`D` のみからなる長さ $ N $ の文字列 $ T $ で表される手順に沿って、グリッド上を $ N $ 回移動しました。 $ i\ =\ 1,\ 2,\ \ldots,\ N $ について、$ T $ の $ i $ 文字目は $ i $ 回目の移動の内容を下記の通り表します。 - `L` のとき、左に $ 1 $ マス移動したことを表す。すなわち、移動前のマスを $ (i,\ j) $ とするとき、移動後のマスは $ (i,\ j-1) $ である。 - `R` のとき、右に $ 1 $ マス移動したことを表す。すなわち、移動前のマスを $ (i,\ j) $ とするとき、移動後のマスは $ (i,\ j+1) $ である。 - `U` のとき、上に $ 1 $ マス移動したことを表す。すなわち、移動前のマスを $ (i,\ j) $ とするとき、移動後のマスは $ (i-1,\ j) $ である。 - `D` のとき、下に $ 1 $ マス移動したことを表す。すなわち、移動前のマスを $ (i,\ j) $ とするとき、移動後のマスは $ (i+1,\ j) $ である。 高橋君の移動経路上のマス（不時着したマスおよび現在いるマスを含む）はいずれも海でないことがわかっています。 高橋君が現在いるマスとしてあり得るものの個数を出力してください。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ N $ $ T $ $ S_1 $ $ S_2 $ $ \vdots $ $ S_H $

答えを出力せよ。

### 制約 - $ H,\ W,\ N $ は整数 - $ 3\ \leq\ H,\ W\ \leq\ 500 $ - $ 1\ \leq\ N\ \leq\ 500 $ - $ T $ は `L` 、`R` 、`U` 、`D` のみからなる長さ $ N $ の文字列 - $ S_i $ は `.` と `#` のみからなる長さ $ W $ の文字列 - 高橋君が現在いるマスとしてあり得るものが少なくとも $ 1 $ 個存在する。 - グリッドの外周のマスはすべて海である。 ### Sample Explanation 1 下記の $ 2 $ つの場合がありえるため、高橋君が現在いるマスとしてあり得るものは $ (3,\ 4) $ と $ (4,\ 5) $ の $ 2 $ 個です。 - マス $ (3,\ 5) $ に不時着し、$ (3,\ 5)\ \rightarrow\ (3,\ 4)\ \rightarrow\ (2,\ 4)\ \rightarrow\ (2,\ 3)\ \rightarrow\ (3,\ 3)\ \rightarrow\ (3,\ 4) $ と移動した場合 - マス $ (4,\ 6) $ に不時着し、$ (4,\ 6)\ \rightarrow\ (4,\ 5)\ \rightarrow\ (3,\ 5)\ \rightarrow\ (3,\ 4)\ \rightarrow\ (4,\ 4)\ \rightarrow\ (4,\ 5) $ と移動した場合