#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define REP(i,m,n) for(int i=(int)m ; i < (int) n ; i++ ) #define rep(i,n) REP(i,0,n) typedef long long ll; typedef pair pint; const int inf=1e9+7; const ll longinf=1LL<<60; const ll mod=1e9+7; int dx[4]={1,0,-1,0} , dy[4]={0,1,0,-1}; typedef vector > mat; int sz; mat mul(mat A,mat B){ mat C(sz,vector(sz)); rep(i,sz)rep(j,sz)rep(k,sz)C[i][j]+=A[i][k]*B[k][j]; return C; } mat pow(mat A,ll k){ mat B(sz,vector(sz)); rep(i,sz)B[i][i]=1; while(k>0){ if(k&1)B=mul(A,B); A=mul(A,A); k/=2; } return B; } int main(){ sz=64; int n,m,t; cin>>n>>m>>t; int sx,sy,gx,gy; cin>>sy>>sx>>gy>>gx; string a[n]; rep(i,n)cin>>a[i]; mat A(sz,vector(sz)); rep(i,n)rep(j,m){ if(a[i][j]=='.'){ int cnt=0; if(a[i][j+1]=='.')cnt++; if(a[i+1][j]=='.')cnt++; if(a[i][j-1]=='.')cnt++; if(a[i-1][j]=='.')cnt++; if(cnt==0){A[8*(i-1)+j-1][8*(i-1)+j-1]=1.0;continue;} if(a[i][j+1]=='.')A[8*(i-1)+j][8*(i-1)+j-1]=1.0/cnt; if(a[i][j-1]=='.')A[8*(i-1)+j-2][8*(i-1)+j-1]=1.0/cnt; if(a[i+1][j]=='.')A[8*i+j-1][8*(i-1)+j-1]=1.0/cnt; if(a[i-1][j]=='.')A[8*(i-2)+j-1][8*(i-1)+j-1]=1.0/cnt; } } A=pow(A,t); cout<