Buhsan y X

Buhsan está estudiando los movimientos de un agente llamado $X$ dentro de una cuadrícula. La cuadrícula es un rectángulo de tamaño $n \times m$ y está formada por los siguientes caracteres: $$ \begin{aligned} \texttt{" "} &:\ \text{celda libre} \\ \texttt{"#"} &:\ \text{obstáculo} \\ \texttt{"I"} &:\ \text{posición inicial de X} \\ \texttt{"F"} &:\ \text{posición final} \end{aligned} $$ $X$ comienza en la celda marcada con $I$ y realiza exactamente $k$ movimientos. En cada movimiento, $X$ puede desplazarse a una de las cuatro celdas adyacentes (arriba, abajo, izquierda o derecha) que se encuentren dentro de la cuadrícula y no contengan un obstáculo. $X$ elegirá en cada paso uno de los posibles movimientos válidos, y todos ellos tendrán la misma probabilidad de ser elegidos. ## Entrada La primera línea contiene un entero $k$ ($1 \le k \le 100$). A continuación se proporcionan las líneas que describen la cuadrícula, todas de la misma longitud. ## Salida Imprime un único número real que represente la probabilidad (en porcentaje) de que $X$ termine en la celda $F$ tras $k$ movimientos, con exactamente dos decimales.

5
#####
#  I#
#   #
# F #
#####

22.22

100
###
#I#
# #
#F#
###

50.00

99
###
#I#
# #
#F#
###

0.00