#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; #define sz size() #define pb push_back #define mp make_pair #define fi first #define se second #define all(c) (c).begin(), (c).end() #define rep(i,a,b) for(ll i=(a);i<(b);++i) #define per(i,a,b) for(ll i=(b-1);i>=(a);--i) #define clr(a, b) memset((a), (b) ,sizeof(a)) #define ctos(c) string(1,c) #define print(x) cout<<#x<<" = "< > mul(vector > v1, vector > v2){ vector > ret(v1.size(),vector(v2[0].size(),0)); for(int i=0;i > powmatrix(vector > vv, vector > v, long long n){ vector > > vvv; vvv.push_back(vv); for(long long i = 0; i < 32; i++){ vvv.push_back(mul(vvv[i],vvv[i])); } vector > v1(vv.size(), vector(vv.size(), 0)); for(int i = 0; i < vv.size(); i++)v1[i][i] = 1.; for(int i = 0; i < 32; i++){ if((n>>i)&1){ v1 = mul(v1,vvv[i]); } } v = mul(v1,v); return v; } long long d[N][N]; int main() { ll r,c,t; cin>>r>>c>>t; ll sy,sx,gy,gx; cin>>sy>>sx; cin>>gy>>gx; vector vs; rep(i,0,r){ string s; cin>>s; vs.pb(s); } if(vs[sy][sx]=='#')return 0; if(vs[gy][gx]=='#')return 0; clr(d,0); rep(y,0,vs.sz){ rep(x,0,vs[0].sz){ if(vs[y][x]=='#')d[y][x]=1; } } vector > v(N*N, vector(1, 0.)); v[sy*c+sx][0] = 1.; vector > vv(N*N, vector(N*N, 0.)); int dy[4]={-1,0,0,1}; int dx[4]={0,-1,1,0}; rep(y,1,r-1){ rep(x,1,c-1){ if(d[y][x]==1)continue; int p = 0; rep(i,0,4){ if(d[y+dy[i]][x+dx[i]]==0)p++; } if(p==0){ vv[y*c+x][y*c+x] = 1.; } else{ rep(i,0,4){ if(d[y+dy[i]][x+dx[i]]==0){ vv[(y+dy[i])*c+(x+dx[i])][y*c+x] = 1./p; } } } } } vector > va = powmatrix(vv,v,t); printf("%20.20f\n", va[gy*c+gx][0]); return 0; }