AT_highrate2025_e ブースの配置

$ H \times W $ のグリッドで表される会場があります。上から $ i $ 行目、左から $ j $ 列目のマスをマス $ (i,j) $ と表します。マス $ (i,j) $ には $ S_{i,j} $ が `#` ならば壁があり、 `.` ならば空であり通行可能です。 あなたはこの会場の空のマスを $ 3 $ マス選んでブースを設置します。以下の条件を満たすようなブースの設置方法は何通りあるか求めてください。ただし、ブース同士は区別しないものとします。 - 以下を両方満たすようなマス $ (r,c) $ が存在する。 - マス $ (r,c) $ には壁もブースもない。 - 全てのブースについて、マス $ (r,c) $ から上下左右に隣接する壁もブースもないマスに移動する操作を $ 0 $ 回以上繰り返すことでそのブースに上下左右に隣接するマスに到達することができる。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ S_{1,1}S_{1,2}\ldots S_{1,W} $ $ S_{2,1}S_{2,2}\ldots S_{2,W} $ $ \vdots $ $ S_{H,1}S_{H,2}\ldots S_{H,W} $

答えを出力せよ。

### Sample Explanation 1 以下の $ 2 $ つの配置が条件を満たします。ただし、ブースがあるマスは `B` で表しています。 ``` #B. #.B B.# B.# #B# #B# ``` どちらの配置もマス $ (2,2) $ から全てのブースに到達可能です。 ### Sample Explanation 2 条件を満たすブースの配置方法は存在しません。したがって、 $ 0 $ を出力してください。 ### Constraints - $ 2\le H,W\le 8 $ - $ H,W $ は整数 - $ S_{i,j} $ は `#` または `.` - $ S_{i,j}= $ `.` を満たす $ (i,j) $ が $ 3 $ つ以上存在する