You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

土拨鼠辰辰最近也在做"放置棋子"的题目, 刘老师看到后想给题目增加点难度.

土拨鼠辰辰 - 放置棋子 - ACjudge

在$n*n$的棋盘上放置$m$个棋子, 一共有多少方案呢? 非常简单, 答案是$C_{n*n}^{m}$种方案, 如果我们加以限制呢?

题目描述

给你一个$n*n$的棋盘, 要求在棋盘上放置$m$个棋子, 所有棋子必须相邻(只能上下左右相邻), 问共有多少方案?

注意: 给你的棋盘上已经放置了一些对方棋子, 我们只能在没有放置棋子的位置放置.

注意: 上述图像上的两个黄色棋子并不相邻.

数据格式

输入格式

第一行两个整数 $n, m$, 表示棋盘的边长和待放置棋子的数量. 接下来输入$n$行, 每行$n$个符号表示棋盘当前的状态, 用#表示该位置已经放置敌方棋子, 用.表示该地方可以放置棋子.

输出格式

一共有多少种方案放置$m$个棋子, 使得各个棋子之间上下左右相邻.

样例

样例1

3 2
#.#
..#
###

2

样例1解释

#@#
.@#
###

#.#
@@#
###

共上述两种方案

样例2

3 2
#.#
.#.
#.#

0

样例3

8 8
########
########
########
########
########
########
########
........

1

数据范围

• $1\ \leq\ n\ \leq\ 8$
• $1\ \leq\ m\ \leq\ 8$