Problem C: 28-搜索与回溯2-魔法卷轴

Problem C: 28-搜索与回溯2-魔法卷轴

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 4  Solved: 1
[Submit] [Status] [Web Board] [Creator:]

Description

小明开宝箱得到一个魔法卷轴，卷轴上有一个n*n大小的格子阵，要在中间摁m个手印才能使用，且要求每两个手印不能再同一行或同一列，格子阵中有些地方是魔法印记，不能摁手印，问一共有多少种使用方法。

Input

第一行输入两个整数n,m(1<=m<=n<=12)

接下去n行代表格子阵的形状，每行有n个字符，@代表可按手印的格子，^代表魔法印记


Output

输出一行为答案

Sample Input

2 1
@^
^@

Sample Output

2

[Submit][Status]