AT_nupc2024_o LRUD Maze

縦 $ N $ 行、横 $ M $ 列からなるグリッドが与えられます。 上から $ i $ 行目、左から $ j $ 列目のマスを $ (i,j) $ と表記します。 グリッドの各マスには `L` , `R` , `U` , `D` のいずれかの文字が書かれており、 今 $ (i,j) $ には $ S_{i,j} $ が書かれています。 このグリッド上では、今いるマスを $ (i,j) $ 、そこに書かれた文字を $ c $ として、以下の移動が可能です。 - $ c = $ `L` かつ $ j\neq 1 $ のとき、マス $ (i,j-1) $ に移動する。 - $ c = $ `R` かつ $ j\neq M $ のとき、マス $ (i,j+1) $ に移動する。 - $ c = $ `U` かつ $ i\neq 1 $ のとき、マス $ (i-1,j) $ に移動する。 - $ c = $ `D` かつ $ i\neq N $ のとき、マス $ (i+1,j) $ に移動する。 さて、あなたはこれから以下の操作を**ちょうど $ 1 $ 回**行います。 - 整数 $ 1 \le i \le N $ と $ 1 \le j \le M $ を選び、 $ (i,j) $ に書かれた文字を `L` , `R` , `U` , `D` のうち $ S_{i,j} $ とは異なる文字に書き換える。 この操作は全部で $ 3NM $ 種類あります。 それらのうち、「操作後のグリッド上で $ (1,1) $ から $ (N,M) $ へ到達可能なもの」の数を求めてください。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ M $ $ S_{1,1} S_{1,2} \dots S_{1,M} $ $ S_{2,1} S_{2,2} \dots S_{2,M} $ $ \vdots $ $ S_{N,1} S_{N,2} \dots S_{N,M} $

標準出力へ答えを一行で出力してください。

### Sample Explanation 1 以下の $ 3 $ 種類が条件を満たします。 - $ (1,2) $ を `R` に変える - $ (2,2) $ を `R` に変える - $ (2,2) $ を `D` に変える ### Sample Explanation 2 答えが $ 0 $ になる場合もあります。 ### Constraints - $ 2 \le N,M \le 1000 $ - $ N,M $ は整数 - $ S_{i,j} $ は `L` , `R` , `U` , `D` のいずれか