1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define PB push_back
typedef long long ll;
typedef long double ld;
#define REP(x,y) for(int x=0;x<(y);x++)
#define ROF(x,y) for(int x=(y);x>0;x--)
#define FOR(x,z,y) for(int x=(z);x<=(y);x++)
#define INT(x) int x;scanf("%d",&x)
#define LL(x) ll x;scanf("%lld",&x)
#define CZ(x) char x;scanf(" %c",&x)
typedef pair<int,int> pii;
typedef pair<int,pii> piii;

bool t[3005][3005];
int n,k;
int wyn;

struct element{
    int a,b,c,d;
    element(int a,int b,int c,int d){
        int t[4]={a,b,c,d};
        sort(t,t+4);
        this->a=t[0];
        this->b=t[1];
        this->c=t[2];
        this->d=t[3];
    }
};

inline bool operator<(const element& l, const element& r)
{
    if(l.a != r.a)return l.a < r.a;
    else if(l.b!=r.b)return l.b < r.b;
    else if(l.c!=r.c)return l.c < r.c;
    else return l.d < r.d;
}

set<element> z;

int tab[5]={-1,-1,-1,-1,-1};
void f(int K){
    FOR(i,1,n)FOR(j,1,n){
            if(!t[i][j]&&(t[i-1][j] || t[i+1][j] || t[i][j-1] || t[i][j+1])){
                if(K==k){
                    if(k==1)wyn++;
                    else{
                        element x = element(tab[1],tab[2],tab[3],3000*i+j);
                        z.insert(x);
                    }
                    //printf("%d %d\n",i-1,j-1);
                }
                else{
                    //printf("-> %d %d",i-1,j-1);
                    t[i][j]=1;
                    tab[K]=3000*i+j;
                    f(K+1);
                    t[i][j]=0;
                }
            }
        }
}


int main(){
    scanf("%d %d",&n,&k);
    string s;
    REP(i,n){
        cin >> s;
        REP(j,n){
            if(s[j]=='#')t[i+1][j+1] = 1;
        }
    }
    f(1);
    if(k>1)wyn=z.size();
    printf("%d",wyn);
}