#include "bits/stdc++.h" using namespace std; #define DEBUG(x) cout<<#x<<": "< #define vl vector #define vii vector< vector > #define vll vector< vector > #define vs vector #define pii pair #define pis pair #define psi pair #define pll pair #define fi first #define se second #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() const int inf = 1000000001; const ll INF = 2e18; #define MOD 1000000007 #define mod 1000000009 #define pi 3.14159265358979323846 #define Sp(p) cout< vec; typedef vector mat; mat mul(mat &A, mat &B) { mat C(A.size(), vec(B[0].size())); for (int i = 0; i < A.size(); i++) { for (int k = 0; k < B.size(); k++) { for (int j = 0; j < B[0].size(); j++) { C[i][j] = C[i][j] + A[i][k] * B[k][j]; } } } return C; } mat pow(mat A, ll n) { mat B(A.size(), vec(A.size())); for (int i = 0; i < A.size(); i++) { B[i][i] = 1; } while (n > 0) { if (n & 1)B = mul(B, A); A = mul(A, A); n >>= 1; } return B; } int main() { int r, c, t; cin >> r >> c >> t; int si, sj, gi, gj; cin >> si >> sj >> gi >> gj; vector > b(r, vector(c)); rep(i, r) { rep(j, c) { cin >> b[i][j]; } } mat a(r*c,vec(1, 0)); a[si * c + sj][0] = 1.0; mat A(r * c, vec(r * c)); rep(i, r) { rep(j, c) { if (b[i][j] == '#') { continue; } int k = i*c + j; int cnt = 0; rep(l, 4) { if (b[i + dy[l]][j + dx[l]] == '.') { cnt++; } } if (cnt == 0) { A[k][k] = 1; continue; } rep(l, 4) { if (b[i + dy[l]][j + dx[l]] == '.') { int nex = (i + dy[l])*c + (j + dx[l]); A[nex][k] = 1.0 / cnt; } } } } mat B = pow(A, t); mat ans = mul(B, a); Sp(ans[gi*c + gj][0]); }