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
#include <cstdio>




char BOARD[3000][4096];
int N, K;
int total_shadows = 0;

inline bool valid(int x, int y) {
    return x>=0 && x<N && y>=0 && y<N;
}

void make_shadow(int x, int y) {
    if (valid(x, y))
        if (BOARD[y][x]=='.') {
            BOARD[y][x] = 'S';
            total_shadows++;
        }
}

void load() {
    scanf("%d%d", &N, &K);
    for (int i=0; i<N; i++)
        scanf("%s", BOARD[i]);
    for (int y=0; y<N; y++) {
        for (int x=0; x<N; x++) {
            if (BOARD[y][x] == '#') {
                make_shadow(x+1, y);
                make_shadow(x-1, y);
                make_shadow(x, y+1);
                make_shadow(x, y-1);
            }
        }
    }
}

void easy_check2() {
    long long p2 = 0;
    for (int y=0; y<N; y++) {
        for (int x=0; x<N; x++) {
            if (BOARD[y][x] == '#')
                continue;
            if (valid(x+1, y) && BOARD[y][x+1] != '#' && BOARD[y][x] != BOARD[y][x+1])
                p2++;
            if (valid(x, y+1) && BOARD[y+1][x] != '#' && BOARD[y][x] != BOARD[y+1][x])
                p2++;
        }
    }
    
    printf("%lld\n", (total_shadows*(total_shadows-1)/2+p2) % 1000000007);
    
    return;
}


int pattern_fits(int x0, int y0, int* px, int* py) {
    int shadowed = 0;
    for (; *px>=0; px++, py++) {
        int x = x0+*px, y = y0+*py;
        if (!valid(x, y))
            return false;
        if (BOARD[y][x] == '#')
            return false;
        if (BOARD[y][x] == 'S')
            shadowed = true;
    }
    return shadowed;
}

int P3X[] = { 0, 0, 0, -9, 0, 1, 2, -9, 0, 1, 0, -9, 0, 1, 1, -9, 1, 1, 0, -9, 0, 0, 1, -9};
int P3Y[] = { 0, 1, 2, -9, 0, 0, 0, -9, 0, 0, 1, -9, 0, 0, 1, -9, 0, 1, 1, -9, 0, 1, 1, -9};
int P2X[] = { 0, 1, -9, 0, 0, -9 };
int P2Y[] = { 0, 0, -9, 0, 1, -9 };
int SH2X[] = { -1, 0, 1, 2, 1, 0,    0, 1, 1, 0, -1, -1 };
int SH2Y[] = { 0, -1, -1, 0, 1, 1,  -1, 0, 1, 2, 1, 0   };


int double_shadows(int x0, int y0, int*px, int* py) {
    int r = 0;
    for (int i=0; i<6; i++, px++, py++) {
        int x = x0+*px;
        int y = y0+*py;
        if (!valid(x, y)) continue;
        if (BOARD[y][x] == 'S')
            r++;
    }
    return r;
}

void brutal() {
    long long result = 0;
    long long to_remove;
    for (int y=0; y<N; y++) {
        for (int x=0; x<N; x++) {
            for (int p3=0; p3<6; p3++) {
                int pf = pattern_fits(x, y, P3X+4*p3, P3Y+4*p3);
                if (pf) {
                    result++;
                }
                if (p3==3) to_remove ++;
            }
            for (int p2=0; p2<2; p2++) {
                int pf = pattern_fits(x, y, P2X+3*p2, P2Y+3*p2);
                if (pf) {
                    result++;
                    result += total_shadows-pf - double_shadows(x, y, SH2X+6*p2, SH2Y+6*p2);
                    result %= 1000000007;
                }
                if (pf==2) {
                    to_remove += total_shadows-pf-double_shadows(x, y, SH2X+6*p2, SH2Y+6*p2);
                }
            }
        }
    }
    
    result += (long long)((total_shadows*(total_shadows-1)%1000000007)*(total_shadows-2)/6);
    result %= 1000000007;
    result += 1000000007 - to_remove;
    result %= 1000000007;
    printf("%lld\n", result);
}


int main() {
    
    load();
    
    if (K==1) 
        printf("%d\n",  total_shadows % 1000000007);
    else if (K==2)
        easy_check2();
    else
        brutal();
    
    return 0;
}