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
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <cstdio>
using namespace std;

#define MAX_N 3200
#define MOD 1000000007

bool T[MAX_N][MAX_N];
char B[MAX_N + 1];

int n;
int n2;
int k;

#define X(a) (a % n)
#define Y(a) (a / n)

inline int isOk(int x, int y) {
    if(x<0 || y<0 || x>=n || y>=n) return 0;
    return !T[x][y] && ((x>0 && T[x-1][y]) || (x<n && T[x+1][y]) || (y>0 && T[x][y-1]) || (y<n && T[x][y+1]));
}

inline int calcAvail() {
    int avail = 0;
    for(int x = 0; x < n; ++x) {
        for(int y = 0; y < n; ++y) {
            avail += isOk(x, y);
        }
    }
    return avail;
}

inline int calc2() {
    int ret = 0;
    int avail = calcAvail();
    for(int x = 0; x < n; ++x) {
        for(int y = 0; y < n; ++y) {
            if(!isOk(x, y)) continue;
            int qwe = -(isOk(x-1, y) + isOk(x+1, y) + isOk(x, y-1) + isOk(x, y+1));
            T[x][y] = 1;
            qwe += isOk(x-1, y) + isOk(x+1, y) + isOk(x, y-1) + isOk(x, y+1);
            T[x][y] = 0;
            ret = (ret + avail + qwe - 1) % MOD;
            avail--;
        }
    }
    return ret;
}

int main() {
    scanf("%d%d", &n, &k);
    n2 = n * n;
    for(int i = 0; i < n; ++i) {
        scanf("%s", B);
        for(int j = 0; j < n; ++j) {
            T[i][j] = (B[j] == '#');
        }
    }

    if(k == 1) {
        printf("%d", calcAvail());
    }
    
    if(k == 2) {
        printf("%d", calc2());
    }

    if(k == 3) {
        int ret = 0;
        for(int a = 0; a < n2; ++a) {
            int xa = X(a), ya = Y(a);
            if(!isOk(xa, ya)) continue;
            T[xa][ya] = 1;
            for(int b = a + 1; b < n2; ++b) {
                int xb = X(b), yb = Y(b);
                if(!isOk(xb, yb)) continue;
                T[xb][yb] = 1;
                for(int c = b + 1; c < n2; ++c) {
                    if(isOk(X(c), Y(c))) {
                        if(++ret >= MOD) ret -= MOD;
                    }
                }
                T[xb][yb] = 0;
            }
            T[xa][ya] = 0;
        }
        printf("%d", ret);
    }

    if(k == 4) {
        int ret = 0;
        for(int a = 0; a < n2; ++a) {
            int xa = X(a), ya = Y(a);
            if(!isOk(xa, ya)) continue;
            T[xa][ya] = 1;
            for(int b = a + 1; b < n2; ++b) {
                int xb = X(b), yb = Y(b);
                if(!isOk(xb, yb)) continue;
                T[xb][yb] = 1;
                for(int c = b + 1; c < n2; ++c) {
                    int xc = X(c), yc = Y(c);
                    if(!isOk(xc, yc)) continue;
                    T[xc][yc] = 1;
                    for(int d = c + 1; d < n2; ++d) {
                        if(isOk(X(d), Y(d))) {
                            if(++ret >= MOD) ret -= MOD;
                        }
                    }
                    T[xc][yc] = 0;
                }
                T[xb][yb] = 0;
            }
            T[xa][ya] = 0;
        }
        printf("%d", ret);
    }

    return 0;
}