配点 : $500$ 点

問題文

$N$ 行 $N$ 列のマス目が与えられ、上から $i$ 番目、左から $j$ 番目のマスは、$S_{i, j}$ が # なら黒く塗られており、. なら白く塗られています。 あなたは白く塗られたマスのうち、ちょうど $K$ 個のマスを選んで赤く塗ります。以下の条件が満たされる塗り方は何通りありますか？

• 赤く塗られたマス(以下赤マスと呼ぶ)は連結である。すなわち、どの赤マスからどの赤マスへも赤マスのみを上下左右に辿って到達できる。

制約

• $1 \leq N \leq 8$
• $1 \leq K \leq 8$
• $S_{i, j}$ は # または .
• $N$ , $K$ は整数である

入力

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

$N$

$K$

$S_{1, 1}S_{1, 2} \dots S_{1, N}$

$S_{2, 1}S_{2, 2} \dots S_{2, N}$

$\vdots$

$S_{N, 1}S_{N, 2} \dots S_{N, N}$

出力

答えを出力せよ。

3
5
#.#
...
..#

5

#.# #@# #@# #@# #@#
@@@ .@@ @@. @@@ @@@
@@# @@# @@# .@# @.#

上のように条件を満たす塗り方が $5$ 通りあります。 赤マスを @ で表しました。

#@#
@.@
@@#

上の塗り方は連結でないので条件を満たしません。 斜めのマス同士は連結していないことに注意してください。

2
2
#.
.#

0

条件を満たす塗り方はありません。

8
8
........
........
........
........
........
........
........
........

64678