To encourage new generations of competitive programmers, the ICPC (Intense Coding Party Committee) is planning new drinking games for the upcoming Shot Contests.

Inspired by old memories of classic Pacman and the Russian Roulette, they wanted to create a new game. One of the ghosts in the original game just moves randomly in the maze. In this new game, both Pacman and the ghost start in the same random position within a 15 square maze without obstacles, but the ghost is hidden until the game ends. Every time the player moves Pacman, the ghost moves to a random adjacent position. After several moves, a button is pressed to reveal the Ghost. If Pacman and the ghost end up in the same position the player lose the game.

While testing the game, they found an issue. Roger, whose debugging skills were second only to his ultimate passion, was called in to find it. After hours of work, Roger identified a problem with the ghost interaction. A programmer had loaded one of the Bomberman's libraries, leaving a bomb that explodes in the starting position after the first move. With each step, the explosion wave expands to all adjacent positions in each one of the four directions. The bomb's expansion wave only affects the ghost. If the ghost lands in the expansion wave, It will remain in that cell until the game ends.

It is important to note that Pacman, the ghost and the expansion wave can go through the border of the maze reaching out the opposite side.

Roger, whose math skills are second only to his debugging skills, tells the committee that the probability of losing the game is really low, but he doesn't have enough time to prove it, he has an ultimate match to play. It is your task to help Roger. For that, you will need to find the probability of losing the game after several moves.