#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } //constexpr long long MAX = 5100000; constexpr long long INF = 1LL << 60; constexpr int inf = 1000000007; constexpr long long mod = 1000000007LL; //constexpr long long mod = 998244353LL; const long double PI = acos((long double)(-1)); using namespace std; typedef unsigned long long ull; typedef long long ll; typedef long double ld; template< class T > struct Matrix { vector< vector< T > > A; Matrix() {} Matrix(size_t n, size_t m) : A(n, vector< T >(m, 0)) {} Matrix(size_t n) : A(n, vector< T >(n, 0)) {}; size_t height() const { return (A.size()); } size_t width() const { return (A[0].size()); } inline const vector< T >& operator[](int k) const { return (A.at(k)); } inline vector< T >& operator[](int k) { return (A.at(k)); } static Matrix I(size_t n) { Matrix mat(n); for (int i = 0; i < n; i++) mat[i][i] = 1; return (mat); } Matrix& operator+=(const Matrix& B) { size_t n = height(), m = width(); assert(n == B.height() && m == B.width()); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) (*this)[i][j] += B[i][j]; return (*this); } Matrix& operator-=(const Matrix& B) { size_t n = height(), m = width(); assert(n == B.height() && m == B.width()); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) (*this)[i][j] -= B[i][j]; return (*this); } Matrix& operator*=(const Matrix& B) { size_t n = height(), m = B.width(), p = width(); assert(p == B.height()); vector< vector< T > > C(n, vector< T >(m, 0)); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) for (int k = 0; k < p; k++) C[i][j] = (C[i][j] + (*this)[i][k] * B[k][j]); //正規化 for (int j = 0; j < m; j++) { T all = 0; for (int i = 0; i < n; i++) { all += C[i][j]; } if (all > 0.5) { for (int i = 0; i < n; i++) { C[i][j] /= all; } } } A.swap(C); return (*this); } Matrix& operator^=(long long k) { Matrix B = Matrix::I(height()); while (k > 0) { if (k & 1) B *= *this; *this *= *this; k >>= 1LL; } A.swap(B.A); return (*this); } Matrix operator+(const Matrix& B) const { return (Matrix(*this) += B); } Matrix operator-(const Matrix& B) const { return (Matrix(*this) -= B); } Matrix operator*(const Matrix& B) const { return (Matrix(*this) *= B); } Matrix operator^(const long long k) const { return (Matrix(*this) ^= k); } friend ostream& operator<<(ostream& os, Matrix& p) { size_t n = p.height(), m = p.width(); for (int i = 0; i < n; i++) { os << "["; for (int j = 0; j < m; j++) { os << p[i][j] << (j + 1 == m ? "]\n" : ","); } } return (os); } T determinant() { Matrix B(*this); assert(width() == height()); T ret = 1; for (int i = 0; i < width(); i++) { int idx = -1; for (int j = i; j < width(); j++) { if (B[j][i] != 0) idx = j; } if (idx == -1) return (0); if (i != idx) { ret *= -1; swap(B[i], B[idx]); } ret *= B[i][i]; T vv = B[i][i]; for (int j = 0; j < width(); j++) { B[i][j] /= vv; } for (int j = i + 1; j < width(); j++) { T a = B[j][i]; for (int k = 0; k < width(); k++) { B[j][k] -= B[i][k] * a; } } } return (ret); } }; int H, W; int cnv(int h, int w) { return h * W + w; } int dh[] = { 1,-1,0,0 }; int dw[] = { 0,0,1,-1 }; using Real = double; int main() { /* cin.tie(nullptr); ios::sync_with_stdio(false); */ ll T; scanf("%d %d %lld", &H, &W, &T); int sh, sw, gh, gw; scanf("%d %d %d %d", &sh, &sw, &gh, &gw); sh--; sw--; gh--; gw--; vector vs; { vector tvs(H); for (int i = 0; i < H; i++) cin >> tvs[i]; vs.resize(H - 2, string(W - 2, ' ')); for (int i = 1; i < H - 1; i++) for (int j = 1; j < W - 1; j++) vs[i - 1][j - 1] = tvs[i][j]; } H -= 2; W -= 2; Matrix mat(H * W); for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { if (vs[i][j] == '#') continue; int cnt = 0; int pos = cnv(i, j); for (int k = 0; k < 4; k++) { int nh = i + dh[k]; int nw = j + dw[k]; if (nh < 0 or nh >= H or nw < 0 or nw >= W) continue; if (vs[nh][nw] == '.') cnt++; } if (cnt == 0) { mat[pos][pos] = 1.0; } else { for (int k = 0; k < 4; k++) { int nh = i + dh[k]; int nw = j + dw[k]; if (nh < 0 or nh >= H or nw < 0 or nw >= W) continue; if (vs[nh][nw] == '.') { int nxt = cnv(nh, nw); mat[nxt][pos] = 1.0 / (Real)cnt; } } } } } mat ^= T; Matrix ini(H * W, 1); ini[cnv(sh, sw)][0] = 1.0; mat *= ini; cout << fixed << setprecision(12) << mat[cnv(gh, gw)][0] << endl; return 0; }