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.