import sequtils,algorithm,math,strutils template times*(n:int,body) = (for _ in 0.." .} proc scan(): int = while true: let k = getchar_unlocked() if k < '0': break result = 10 * result + k.ord - '0'.ord let h = scan() - 2 let w = scan() - 2 var t = scan() let (sy,sx) = (scan()-1,scan()-1) let (gy,gx) = (scan()-1,scan()-1) if (sx + sy + gx + gy) mod 2 != t mod 2: quit "0.0",0 var B = newSeqWith(w,newSeq[char](h)) t .min= 999999 (w+3).times:discard getchar_unlocked() for y in 0..= w or ny >= h : continue if B[nx][ny] == '#' : continue cnt += 1 if cnt == 0: M[encode(x,y),encode(x,y)] = 1.0 continue for d in dxdy4: let nx = x + d.x let ny = y + d.y if nx < 0 or ny < 0 or nx >= w or ny >= h : continue if B[nx][ny] == '#' : continue M[encode(x,y),encode(nx,ny)] = 1.0 / cnt.float let SM = newSparseMatrix(M) echo ((SM^t)*I)[encode(gx,gy)]