E - Lamps 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 500 点

問題文

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

今からあなたはこのマス目のうち 0 個以上の散らかっていないマスに照明を置きます。

照明は置かれたマスの上下左右の 4 方向に、マス目の端もしくは最初に散らかっているマスにぶつかる直前まで照らします (散らかっているマスは照らされません)。照明は、置かれたマス自身も照らします。

整数 H, W と H 個の長さ W の文字列 S_i が与えられます。 S_i の j 文字目が . のとき、上から i 行目、左から j 列目のマスは散らかっていません。S_i の j 文字目が # のとき、上から i 行目、左から j 列目のマスは散らかっています。

散らかっていないマスの個数を K 個だとすると、照明の置き方は全部で 2^K 通りあります。 この 2^K 通りそれぞれについて、1 個以上の照明によって照らされるマスの個数を計算したときの総和を 1,000,000,007 で割ったあまりを求めてください。

制約

  • 1 \leq H \leq 2000
  • 1 \leq W \leq 2000
  • S_i は . と # のみからなる長さ W の文字列

入力

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

H W
S_1
:
S_H

出力

2^K 通りそれぞれについて、1 個以上の照明によって照らされるマスの個数を計算したときの総和を 1,000,000,007 で割ったあまりを出力せよ。

入力例 1

1 5
..#..

出力例 1

48

全部で照明の置き方は 16 通りあります。

  • このうち 9 通り (左から 1 番目か 2 番目の少なくとも一方に照明が置かれている、かつ左から 4 番目か 5 番目の少なくとも一方に照明が置かれている) では、4 マスが照らされます。
  • このうち 3 通り (左から 1 番目か 2 番目の少なくとも一方に照明が置かれている、かつ左から 4 番目と 5 番目のどちらにも照明が置かれていない) では、2 マスが照らされます。
  • このうち 3 通り (左から 4 番目か 5 番目の少なくとも一方に照明が置かれている、かつ左から 1 番目と 2 番目のどちらにも照明が置かれていない) では、2 マスが照らされます。
  • このうち 1 通り (照明が 1 つも置かれていない) では、0 マスが照らされます。

求める総和は 4 \times 9 + 2 \times 3 + 2 \times 3 + 0 \times 1 = 48 となります。

入力例 2

2 3
..#
#..

出力例 2

52

Score : 500 points

Problem Statement

We have a grid with H horizontal rows and W vertical columns of squares, where each square is tidy or untidy.

You will now place lamps on zero or more tidy squares in this grid.

A lamp will lighten the squares in each of the four directions - up, down, left, and right - to the point just before an edge of the grid or an untidy square is reached for the first time (the untidy square will not be lighted). The lamp will also lighten the square on which it is placed.

Given are integers H, W, and H strings S_i of length W each. If the j-th character of S_i is ., the square at the i-th row from the top and the j-th column from the left is tidy; if the j-th character of S_i is #, the square at the i-th row from the top and the j-th column from the left is untidy.

Let K be the number of tidy squares. There are 2^K ways to place the lamps in total. Assume that, for each of these 2^K ways, the number of squares lightened by one or more lamps is computed. Find the sum of those numbers modulo 1,000,000,007.

Constraints

  • 1 \leq H \leq 2000
  • 1 \leq W \leq 2000
  • S_i is a string of length W consisting of . and #.

Input

Input is given from Standard Input in the following format:

H W
S_1
:
S_H

Output

Print the sum, modulo 1,000,000,007, of the numbers of squares lightened by one or more lamps over the 2^K ways to place the lamps.

Sample Input 1

1 5
..#..

Sample Output 1

48

There are 16 ways to place the lamps in total.

  • In 9 of the ways (where at least one of the 1-st and 2-nd squares from the left contains a lamp and at least one of the 4-th and 5-th squares from the left contains a lamp), 4 squares will be lighted.
  • In 3 of the ways (where at least one of the 1-st and 2-nd squares from the left contains a lamp but none of the 4-th and 5-th squares from the left contains a lamp), 2 squares will be lighted.
  • In another 3 of the ways (where none of the 1-st and 2-nd squares from the left contains a lamp but at least one of the 4-th and 5-th squares from the left contains a lamp), 2 squares will be lighted.
  • In 1 of the ways (where no square contains a lamp), 0 squares will be lighted.

The sum in question is 4 \times 9 + 2 \times 3 + 2 \times 3 + 0 \times 1 = 48.

Sample Input 2

2 3
..#
#..

Sample Output 2

52