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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <cstdio>
#include <cstring>

#define DBG(...) fprintf(stderr, __VA_ARGS__)

typedef int I;
typedef long long L;

static const I MOD = 1000000000 + 7;

static const I W = 3008;
static const I LEFT = -1;
static const I RIGHT = 1;
static const I TOP = -W;
static const I BOTTOM = W;

static const I FILL = 1;
static const I EMPTY = 2;
static const I XONE = 4;
static const I XTWO = 8;
static const I XTHREE = 16;

struct E {
        I v;
        I n2;
        I n3;
};

static E tab[W*W];

static inline I mm(L a, L b) {
        return (a * b) % MOD;
}

static inline I nt(I a, I b) {
        if (a < b)
                return 0;
        L ret = 1;
        for (I x=1; x<=b; ++x) {
                ret *= a - x + 1;
                ret /= x;
                ret = ret % MOD;
        }
        return ret;
}

static I calc(const I n, const I k) {
        // jedynki
        I sum1 = 0;
        for (I y=0; y<n; ++y) {
                E* row = tab + y * W + W;
                for (I x=0; x<n; ++x) {
                        if (row[x].v != EMPTY)
                                continue;
                        if ((row[x + LEFT].v | row[x + RIGHT].v | row[x + TOP].v | row[x + BOTTOM].v) & FILL) {
                                row[x].v = XONE;
                                ++ sum1;
                        }
                }
        }
        if (k == 1)
                return sum1;
        // dwojki
        I sum2 = 0;
        I sum211 = 0;
        I sum2111 = 0;
        I sum21111 = 0;
        for (I y=0; y<n; ++y) {
                E* row = tab + y * W + W;
                for (I x=0; x<n; ++x) {
                        if (row[x].v != EMPTY)
                                continue;
                        I sum = 0;
                        sum += (row[x + LEFT].v & XONE) ? 1 : 0;
                        sum += (row[x + RIGHT].v & XONE) ? 1 : 0;
                        sum += (row[x + TOP].v & XONE) ? 1 : 0;
                        sum += (row[x + BOTTOM].v & XONE) ? 1 : 0;
                        if (sum) {
                                row[x].v = XTWO;
                                row[x].n2 = sum;
                                sum2 += sum;
                        }
                        if (sum == 2)
                                ++sum211;
                        if (sum == 3)
                                ++sum2111;
                        if (sum == 4)
                                ++sum21111;
                }
        }
        if (k == 2)
                return (sum2 + nt(sum1, 2)) % MOD;
        // trojki
        I sum3 = 0;
        I sum122 = 0;
        I sum1222 = 0;
        for (I y=0; y<n; ++y) {
                E* row = tab + y * W + W;
                for (I x=0; x<n; ++x) {
                        if (row[x].v & XONE) {
                                // 122 1222
                                I sum = 0;
                                sum += (row[x + LEFT].v & XTWO) ? 1 : 0;
                                sum += (row[x + RIGHT].v & XTWO) ? 1 : 0;
                                sum += (row[x + TOP].v & XTWO) ? 1 : 0;
                                sum += (row[x + BOTTOM].v & XTWO) ? 1 : 0;
                                if (sum == 2)
                                        ++sum122;
                                if (sum == 3)
                                        ++sum1222;
                        }
                        if (row[x].v != EMPTY && row[x].v != XTWO)
                                continue;
                        // 321
                        I sum = 0;
                        sum += row[x + LEFT].n2;
                        sum += row[x + RIGHT].n2;
                        sum += row[x + TOP].n2;
                        sum += row[x + BOTTOM].n2;
                        if (sum) {
                                row[x].v |= XTHREE;
                                row[x].n3 = sum;
                                sum3 += sum;
                        }
                }
        }
        if (k == 3) {
                L ret = sum3;
                ret += nt(sum1, 3);
                ret += sum122;
                ret += sum1222 * 3;
                ret += mm(sum2, (sum1 - 1));
                ret -= sum211;
                ret -= (L)3 * sum2111;
                ret -= (L)6 * sum21111;
                return ret % MOD;
        }
        return 0;
}

int main() {
        memset(tab, 0, sizeof(tab));
        I n, k;
        scanf("%u %u\n", &n, &k);
        char c;
        for (I y=0; y<n; ++y) {
                for (I x=0; x<n; ++x) {
                        scanf("%c\n", &c);
                        tab[x + y * W + W].v = (c == '#') ? FILL : EMPTY;
                }
        }
        printf("%u\n", calc(n, k));
        return 0;
}