acm International Collegiate Programming Contest

Links

A B C D E F G H

Problem E

桂馬

NM 列の格子状に点が並んでいる. 各点を,その行番号 i (1 ≤ iN) と列番号 j (1 ≤ jM) を用いて Pi, j と呼ぶことにする.

各点は白か黒に塗られている.白い点からなる集合 T のうち,以下の制約を満たすものの個数を計算せよ.

  • i ∈ {3, 4,..., N}, ∀j ∈ {2, 3,..., M}, Pi, jTPi -2, j -1T,
  • i ∈ {3, 4,..., N}, ∀j ∈ {1, 2,..., M−1}, Pi, jTPi -2, j +1T.

例えば下図で☆の位置にある点を選ぶと,×の付けられた2つの点はどちらも選ぶことができない.

将棋を知っている人は, ☆と×をつけた点の相対位置と桂馬の動きの共通性に気づくだろう.

答えは巨大になる可能性があるため, 109+7 で割った余りを出力せよ.

Input

入力は複数のデータセットからなる. 各データセットは次の形式で表される.

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 個以内である.

Output

各データセットについて,条件を満たす部分集合の個数を 109+7 で割った余りを一行に出力せよ.

Sample Input

3 2
.#
##
#.
3 3
.#.
#.#
..#
6 5
.#..#
...#.
#....
..#.#
#....
..#..
0 0

Output for the Sample Input

3
20
103320
(End of Problem E) A B C D E F G H