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
#include <bits/stdc++.h>

using namespace std;

long long M=1000000007;
char s[3010][3010];
int tab[3010][3010];
bool dost[3010][3010];
/*bool odw1[3010][3010];
bool odw2[3010][3010];
bool odw3[3010][3010];*/
//queue <pair <int, int> > q_dost;
long long liczba_dost_w1=0;
//vector < pair <int,int> > o_ile_zw1[10];

long long x[250010][5];
long long newton(int n,int k)
{
    return x[n][k]%1000000007;
}

int main()
{
    int n,k;
    scanf("%d %d",&n,&k);
    for(int i=0;i<=250000;++i)
    {
        for(int j=0;j<=4;++j)
        {
            if(j==0) x[i][j]=1;
            else if(i==j) x[i][j]=1;
            else if(i>j) x[i][j] =( x[i-1][j]+x[i-1][j-1] )%M;
        }
    }
    for(int i=0;i<n;++i)
    {
        scanf("%s",s[i]);
    }
    long long wynik=0;
    for(int i=n;i>=0;--i)
    {
        for(int j=n;j>=0;--j)
        {
            if(i!=0 && j!=0)s[i][j]=s[i-1][j-1];
            else s[i][j]=0;
        }
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
        {
            if(s[i][j]=='.')
            {
                if(s[i-1][j]=='#' || s[i+1][j]=='#' || s[i][j+1]=='#' || s[i][j-1]=='#' )
                {
                    dost[i][j]=true;
  //                  q_dost.push(make_pair(i,j));
                    liczba_dost_w1++;
                }
            }
        }
    }
    if(k==1)
    {
        printf("%lld\n",liczba_dost_w1);
        return 0;
    }
   /* while(q_dost.empty()==false)
    {
        int i=q_dost.front().first;
        int j=q_dost.front().second;
        int akt=0;
        if(s[i-1][j]=='.' && dost[i][j]==false)akt++;
        if(s[i+1][j]=='.' && dost[i][j]==false)akt++;
        if(s[i][j-1]=='.' && dost[i][j]==false)akt++;
        if(s[i][j+1]=='.' && dost[i][j]==false)akt++;
        o_ile_zw1[akt].push_back(make_pair(i,j));
        q_dost.pop();
    }
    int maxi_1=0;
    for(int i=1;i<=4;++i)
    {
        if(o_ile_zw1[i].size()>0)maxi_1=i;
    }*/
    long long maxi_pas=0;
    long long maxi_pas2=0;
    long long suma_maxi_pas=0;
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
        {
                if(s[i][j]=='.' && dost[i][j]==false)
                {
                    if(s[i-1][j]=='.' && dost[i-1][j]==true)tab[i][j]++;
                    if(s[i+1][j]=='.' && dost[i+1][j]==true)tab[i][j]++;
                    if(s[i][j-1]=='.' && dost[i][j-1]==true)tab[i][j]++;
                    if(s[i][j+1]=='.' && dost[i][j+1]==true)tab[i][j]++;
                    if(maxi_pas<tab[i][j])
                    {
                        maxi_pas2=maxi_pas;
                        maxi_pas=tab[i][j];
                    }
                    else
                    {
                        if(maxi_pas2<tab[i][j])maxi_pas2=tab[i][j];
                    }
                    suma_maxi_pas+=tab[i][j];
                }
        }
    }

    wynik=( ( ( (liczba_dost_w1) * (liczba_dost_w1-1) ) /2 + suma_maxi_pas) +M )%M;
    if(k==2)
    {
        printf("%lld\n",wynik);
        return 0;
    }
  // long long f=newton(liczba_dost_w1,4);
    wynik=( ( newton(liczba_dost_w1,3) )+( ( ( ( (maxi_pas)*(liczba_dost_w1-1) )+M)%M)/2 )+((liczba_dost_w1-2)*( ( ( (maxi_pas)*(maxi_pas-1) +M) %M)/2 ))+M)%M;
    if(k==3)
    {
        printf("%lld\n",wynik);
        return 0;
    }

    wynik=( ( newton(liczba_dost_w1,4) ) + ( ( (maxi_pas) * (maxi_pas2) +M)%M ) + ( ( (maxi_pas) * (newton(liczba_dost_w1-1,2))-maxi_pas +M )%M ) + ( ( (maxi_pas2) * (newton(liczba_dost_w1-1,2))-maxi_pas2 +M)%M ) +M)%M;
    if(k==4)
    {
        printf("%lld\n",wynik);
        return 0;
    }
    return 0;
}