31947번 - 사다리 게임 만들기 스페셜 저지

SCSC의 개발자 철수는 사다리 게임을 만드는 프로그램을 개발했다! 컴퓨터는 $N$개의 세로선으로 구성된 사다리에 다음과 같은 동작을 $M$번 반복해 사다리를 완성한다.

• $N-1$개의 이웃한 두 세로선 사이 구간 중 하나를 무작위로 골라 무작위의 높이에 새로운 가로선을 추가한다. 각 구간이 선택될 확률은 모두 $\displaystyle \frac{1}{N-1}$로 같다. 가로선이 추가되는 높이도 가로선을 그릴 수 있는 범위에서 균등 분포를 따라 무작위로 선택된다. 이전에 추가한 가로선과 완전히 높이가 같다면 높이를 새로 선택한다.

프로그램이 완성되자 지환이를 포함한 SCSC 부원 네 명이 $N=4$, $M=3$을 입력으로 사다리 게임을 진행했다. 예를 들어 아래와 같은 사다리가 생성될 수 있다.

부원들은 각자 위쪽 지점 A, B, C, D 중 하나를 골라 1등이 돈을 얻는 게임을 계속했다. 지환이는 항상 D를 골랐지만 한 번도 1등이 나오지 않아 돈을 모두 잃었고, D가 1등이 될 확률보다 4등이 될 확률이 훨씬 높은 것 같다며 화를 냈다. 그런데 지환이의 말이 사실이었다!

따라서 개발자 철수는 확률을 보정하여 게임을 다시 만들고자 한다. 그런데 철수는 코딩에는 매우 익숙하지만 수학은 하나도 모르기 때문에 확률을 계산하지 못한다. 철수를 대신해 지환이가 1등이 될 확률을 계산해주자!

첫째 줄에 세로선의 수 $N$과 추가되는 가로선의 수 $M$이 공백으로 구분되어 주어진다. $(2 \le N \le 500;$ $0 \le M \le 10 000)$

둘째 줄에 위쪽의 지환이가 고른 지점의 위치 $S$와 아래쪽의 1등 지점의 위치 $E$가 공백으로 구분되어 주어진다. $(1 \le S, E \le N)$

지환이가 고른 지점과 1등 지점의 위치는 각각 맨 왼쪽부터 $S$번째 사다리, $E$번째 사다리를 의미한다.

첫째 줄에 지환이가 1등이 될 확률을 출력한다. 절대/상대 오차는 $10^{-6}$까지 허용한다.