브라우니안 곰

Ursula Major 박사는 북아메리카 여러 지역에서 그리즐리 곰이라고 부르는 갈색곰을 연구하는 세계적인 전문가다. 박사는 매우 희귀한 갈색곰 아종인 브라우니안 곰을 발견한 것으로 가장 유명하다. 이 곰의 먹이 활동은 규칙성과 무작위성이 뒤섞인 모습을 보인다.

현재 박사는 동서로 뻗은 좁은 땅에 사는 브라우니안 곰 한 쌍을 연구하고 있다. 이 땅에는 곰이 베리를 찾을 수 있는 등간격 지점이 $n$개 있고, 박사는 이를 서쪽에서 동쪽으로 $1, 2, \ldots, n$번으로 번호 붙였다. 매일 아침 각 곰은 한 지점에서 깨어나 동쪽이나 서쪽의 인접 지점으로 이동한다. 두 방향으로 이동할 확률은 각각 정확히 50%다. 곰이 끝 지점($1$ 또는 $n$)에서 하루를 시작하면, 유일한 이웃 지점으로 가거나 제자리에 머무르는 것 중 하나를 무작위로 고른다. 곰은 선택한 지점에서 그날 하루 베리를 찾고, 그날 밤에도 그곳에서 잔다. 다음 날 아침 같은 과정이 반복된다.

박사는 두 곰이 같은 지점에서 함께 베리를 찾는 날에 특히 관심이 많다. 그래서 최대 한 달(또는 연구비가 떨어질 때까지) 관찰할 계획이다. 첫 관찰일 아침에 두 곰은 서로 다른 지점에서 깨어난다. 실험 기간 중 적어도 하루는 두 곰이 함께 베리를 찾을 확률을 구하라.

두 곰은 함께 베리를 찾지 않고 서로를 지나칠 수 있다. 예를 들어 어느 날 두 곰이 지점 $4$와 $5$에서 출발해, 지점 $4$의 곰은 동쪽으로, 지점 $5$의 곰은 서쪽으로 움직이면, 그날 아침 두 곰은 함께 베리를 찾지 않고 서로 지나친다.

입력은 공백으로 구분된 정수 네 개 $n$ $x$ $y$ $d$가 한 줄에 주어진다. $n$($2 \leq n \leq 100$)은 지점의 개수다. $x$와 $y$($1 \leq x, y \leq n$, $x \neq y$)는 첫 관찰일 아침에 두 곰이 깨어나는 지점이다. $d$($1 \leq d \leq 31$)는 관찰 일수다.

두 곰이 $d$일의 관찰 기간 중 적어도 하루 함께 베리를 찾을 확률을 기약분수 $a/b$ 꼴로 한 줄에 출력하라. $a$는 0 이상의 정수이고, $b$는 양의 정수다.