#include using namespace std; const int dx[] = {0, 0, -1, 1}; const int dy[] = {1, -1, 0, 0}; using row = std::vector; using matrix = std::vector; //(A * B) mod matrix matrixMul(matrix &A, matrix &B, const int mod) { const int asz = A.size(); const int bsz = B.size(); const int bcolsz = B.front().size(); matrix res(asz, row(bcolsz, 0)); for (int i = 0; i < asz; i++) { for (int k = 0; k < bsz; k++) { for (int j = 0; j < bcolsz; j++) { (res[i][j] += A[i][k] * B[k][j]); } } } return res; } //(mat^p) mod matrix matPowMod(matrix mat, long long p, const int mod) { const int matsz = mat.size(); assert((int)mat.front().size() == matsz);//must square matrix!! matrix res(matsz, row(matsz, 0)); for (int i = 0; i < matsz; i++) { res[i][i] = 1; } while (p) { if (p & 1) res = matrixMul(res, mat, mod); mat = matrixMul(mat, mat, mod); p >>= 1; } return res; } matrix make_matrix(int r, int c) { return matrix(r, row(c)); } int main() { int r, c, t; cin >> r >> c >> t; int sy, sx, gy, gx; cin >> sy >> sx >> gy >> gx; auto mat = make_matrix(100, 100); vector B(r); for_each(begin(B), end(B), [](auto &e){cin >> e;}); for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { const int rIdx = i * 10 + j; if (B[i][j] == '.') { int cnt = 0; for (int k = 0; k < 4; k++) { cnt += B[i + dy[k]][j + dx[k]] == '.'; } if (cnt) { for (int k = 0; k < 4; k++) { const int cIdx = (i + dy[k]) * 10 + j + dx[k]; mat[rIdx][cIdx] = 1. * (B[i + dy[k]][j + dx[k]] == '.') / cnt; } } else { mat[rIdx][rIdx] = 1; } } } } auto mat2 = matPowMod(mat, t, -1); cout << fixed << setprecision(10) << mat2[sy * 10 + sx][gy * 10 + gx] << endl;; }