配点: 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 有 2 个白色方块
小課題
- (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 约束。