U244430 [5002IOCS] 互不侵犯++

在 $N \times M$ 的棋盘里面放若干个国王（可以不放），使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。 特别地，一些格子上面因为特性不能放置国王。我们用一个 $N \times M$ 的矩阵描述棋盘，若一个位置是 `.` 则可以放国王，若是 `#` 则不能放置国王。 由于答案很大，你需要将答案对 $10^9+7$ 取模。

第一行两个正整数 $N,M$。 此后 $N$ 行，每行一个长为 $M$ 由 `.` 或 `#` 组成的字符串，表示棋盘的一行。

一行一个非负整数，表示答案对 $10^9+7$ 取模的结果。

**本题捆绑测试。** $Subtask1(1pt)$，$1 \le N,M \le 4$，时限 `0.1s`。 $Subtask2(5pt)$，$1 \le N,M \le 9$，时限 `0.1s`。 $Subtask3(30pts)$，$1 \le N,M \le 17$，时限 `1s`。 $Subtask4(64pts)$，时限 `2s`。 对于 $100\%$ 的数据，$1 \le N,M \le 24$。 Source Name: 「競プロ典型90問」23日目