나이트가 체스판을 벗어나지 않을 확률

크기가 $N \times N$인 체스판 위에 나이트가 하나 놓여 있다. 나이트는 매 턴마다 여덟 방향 중 하나를 각각 $1/8$의 확률로 골라 그쪽으로 이동한다.

체스판의 가장 윗 행이 1번 행, 가장 아랫 행이 $N$번 행이고, 가장 왼쪽 열이 1번 열, 가장 오른쪽 열이 $N$번 열이다. 좌표 $(x, y)$는 $x$행 $y$열을 뜻한다.

나이트가 $(x, y)$에 있으면 이동할 수 있는 칸은 $(x+1, y+2)$, $(x+2, y+1)$, $(x+2, y-1)$, $(x+1, y-2)$, $(x-1, y-2)$, $(x-2, y-1)$, $(x-2, y+1)$, $(x-1, y+2)$의 여덟 곳이다. 체스판 밖으로 나가는 방향도 나머지와 똑같은 확률로 뽑힌다.

나이트가 체스판 밖으로 나가면 그 자리에서 멈추고 다시 안으로 들어오지 못한다. 시작 좌표와 이동 횟수 $K$가 주어질 때, $K$번 이동한 뒤에도 나이트가 체스판 위에 남아 있을 확률을 구하는 프로그램을 작성하시오.

첫째 줄에 $N$, 나이트의 시작 좌표 $x$와 $y$, 이동 횟수 $K$가 공백으로 구분되어 주어진다. ($1 \le N \le 50$, $1 \le x, y \le N$, $0 \le K \le 50$)

첫째 줄에 $K$번 이동한 뒤 나이트가 체스판 위에 있을 확률을 소수점 아래 10자리까지 출력한다. 정답은 분모가 $8^K$인 유리수이므로 그 정확한 값을 소수점 아래 11번째 자리에서 반올림하고, 소수점 아래 10자리를 빠짐없이 적는다. 확률이 1이면 1.0000000000, 0이면 0.0000000000을 출력한다.