N 行 M 列の格子状に点が並んでいる.
各点を,その行番号 i (1 ≤ i ≤ N)
と列番号 j (1 ≤ j ≤ M)
を用いて Pi, j と呼ぶことにする.
各点は白か黒に塗られている.白い点からなる集合 T のうち,以下の制約を満たすものの個数を計算せよ.
- ∀i ∈ {3, 4,..., N},
∀j ∈ {2, 3,..., M},
Pi, j ∈ T ⇒
Pi -2, j -1 ∉ T,
- ∀i ∈ {3, 4,..., N},
∀j ∈ {1, 2,..., M−1},
Pi, j ∈ T ⇒
Pi -2, j +1 ∉ T.
例えば下図で☆の位置にある点を選ぶと,×の付けられた2つの点はどちらも選ぶことができない.
将棋を知っている人は,
☆と×をつけた点の相対位置と桂馬の動きの共通性に気づくだろう.
答えは巨大になる可能性があるため, 109+7 で割った余りを出力せよ.
入力は複数のデータセットからなる.
各データセットは次の形式で表される.
N M
a1,1 ... a1,M
...
aN,1 ... aN,M
各データセットの一行目には二つの整数 N (2 ≤ N ≤ 60) と M (2 ≤ M ≤ 60) が与えられ,それぞれ行数と列数を表す.
続く N 行にはそれぞれ M 文字が与えられる.
i 番目の文字列の j 文字目 ai,j
は点 Pi, j の色を表し,'.' は白色,'#' は黒色であることを示す.
入力の終わりは,二つのゼロのみからなる行で表される.
データセットは 100 個以内である.