AT_hhkb2020_e Lamps

[problemUrl]: https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_e 縦 $ 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 $ で割ったあまりを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ S_1 $ $ : $ $ S_H $

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

### 制約 - $ 1\ \leq\ H\ \leq\ 2000 $ - $ 1\ \leq\ W\ \leq\ 2000 $ - $ S_i $ は `.` と `#` のみからなる長さ $ W $ の文字列 ### Sample Explanation 1 全部で照明の置き方は $ 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 $ となります。