023 - Avoid War（★7）
解説
/ 
/ 
実行時間制限: 8 sec / メモリ制限: 2048 MiB
配点: 7 点
問題文
縦 H マス、横 W マスからなるグリッドがあり、上から i 行目・左から j 列目のマスを (i,j) で表します。
各マスには色が塗られており、マス (i,j) の色は C_{i,j} が # のとき黒、C_{i,j} が . のとき白です。
あなたはいくつかの白マスを選び（1 つも選ばなくても良い）、キングの駒を置きます。 キング同士が互いに攻撃し合わない（後述）ような置き方の数を、10^9+7 で割った余りを求めてください。
ただし、ある 2 つの置き方が異なるとは、 「ある白マスが存在して、片方ではキングが置かれており、もう片方では置かれていない」 ことを言います。
「キング同士が互いに攻撃し合わない」とは
キングが置かれている任意の異なる 2 マス (i,j) および (k,l) において、 |i-k|>1 または |j-l|>1 が成り立つことを言います。制約
- 1 \leq H,W \leq 24
- H,W は整数
- C_{i,j} は
#または. - 少なくとも 1 つの白マスが存在する
小課題
- (1 点) 1 \leq H,W \leq 4
- (1 点) 1 \leq H,W \leq 9
- (2 点) 1 \leq H,W \leq 17
- (3 点) 追加の制約はない。
入力
入力は以下の形式で標準入力から与えられます。
H W
C_{1,1}\cdots C_{1,W}
\vdots
C_{H,1}\cdots C_{H,W}
出力
条件を満たす置き方の数を、10^9+7 で割った余りを出力してください。
入力例 1
1 3 ...
出力例 1
5
以下の 5 通りがあります。( o はキングを置いたマスを表します。)
... o.. .o. ..o o.o
これは小課題 1,2,3,4 の制約を満たします。
入力例 2
3 3 .#. #.. .##
出力例 2
13
以下の 13 通りがあります。( o はキングを置いたマスを表します。)
.#. o#. .#o .#. .#. .#. o#o #.. #.. #.. #o. #.o #.. #.. .## .## .## .## .## o## .## o#. o#. .#o .#. o#o o#. #.o #.. #.. #.o #.. #.o .## o## o## o## o## o##
これは小課題 1,2,3,4 の制約を満たします。
入力例 3
8 9 ######.## ####..##. ..#...#.. ###...### #....##.# .##...... #.####..# #.#######
出力例 3
273768
これは小課題 2,3,4 の制約を満たします。
入力例 4
17 17 .####...#.....#.# .#....#.#####...# #...##.##...#..## ..#..####..#...## .#..#..#.#.##...# .#.#.#...#.##..#. #...#..#..##..### ###.#..###..###.. ...#.##.##.#....# ..####....#.#...# .##...##.#.#...#. ..########...###. #..##....#....... ##.##..###.#.##.. .##....#........# ....#####..##.#.. .###...##..##.#..
出力例 4
314465173
10^9+7 で割った余りを出力してください。
これは小課題 3,4 の制約を満たします。
入力例 5
22 18 .##.##.#.#.#...##. ####.#..###.#.#..# #####.##...##.###. ...#.#.#.##.##.### ..#.##.#.#....#... #.###.##....###..# ....#####...#...#. .#..##..#..###.... ....#..##.#.#..#.# ###.#.....#..##.#. #..#..#.#.##..###. #...#....##..###.. ..#...#..###..##.. .#....#.#.#..###.# ##.#.#..#..###..## ....###.##.##.##.. #...####.#.#..##.. ..#.###.###.###.## #...##.#.#.#...#.# #..###..########.. #.##.#####.#..#.## #..#........#...#.
出力例 5
47296634
これは小課題 4 の制約を満たします。