#hhkb2020b. [hhkb2020_b]Futon

[hhkb2020_b]Futon

問題文

HH 行、横 WW 列からなるマス目があり、それぞれのマスは散らかっているか散らかっていないかのどちらかです。

今からあなたはこのマス目に 11 つ布団を敷きます。

縦または横に隣接するマス目の内部の 22 マスであって、いずれのマスも散らかっていない場所に布団を敷くことができます。

整数 H,WH, WHH 個の長さ WW の文字列 SiS_i が与えられます。 SiS_ijj 文字目が . のとき、上から ii 行目、左から jj 列目のマスは散らかっていません。SiS_ijj 文字目が # のとき、上から ii 行目、左から jj 列目のマスは散らかっています。

布団を敷く場所の選び方は全部で何通りあるか求めてください。

制約

  • 2leqHleq1002 \\leq H \\leq 100
  • 2leqWleq1002 \\leq W \\leq 100
  • SiS_i.# のみからなる長さ WW の文字列

入力

入力は以下の形式で標準入力から与えられる。

HH WW S1S_1 :: SHS_H

出力

布団を敷く場所の選び方の総数を出力せよ。


入力例 1

2 3
..#
#..

出力例 1

3

次の 33 通りの選び方があります。

  • 上から 11 行目の左から 11 列目と 22 列目
  • 上から 22 行目の左から 22 列目と 33 列目
  • 左から 22 列目の上から 11 行目と 22 行目

入力例 2

2 2
.#
#.

出力例 2

0