안전지대

사루만의 군대가 헬름 협곡을 포위하고 성벽에 화살을 퍼붓고 있다. 로한군에게는 성벽의 한 구간만 막을 수 있는 방패밖에 없다. 당신은 세오덴 왕의 병사이고, 다음 화살 세례가 떨어지기 전에 방패가 지키는 구간으로 몸을 피해야 한다.

성벽의 구간에는 왼쪽부터 $0$번부터 $N-1$번까지 번호가 붙어 있고, 당신은 지금 $J$번 구간에 서 있다. 방패는 $P$번부터 $Q$번까지를 막아 준다. 다음 화살이 떨어지기 전까지 정확히 $K$번 이동할 수 있고, 한 번의 이동은 왼쪽으로 한 칸 또는 오른쪽으로 한 칸이다. 성벽이 흔들려서 제자리에 서 있을 수는 없다.

$K$번 이동한 뒤 $P$번과 $Q$번 사이에 서 있게 되는 이동 방법이 몇 가지인지 세어라. 이동 순서가 다르면 다른 방법으로 센다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄에 $N$, $P$, $Q$, $J$, $K$가 공백으로 구분되어 주어진다. $N$은 성벽의 길이, $P$와 $Q$는 안전 구간의 양 끝, $J$는 시작 위치, $K$는 이동 횟수이다. $N$이 $0$인 줄은 입력의 끝을 뜻하며, 이 줄에 대해서는 아무것도 출력하지 않는다.

성벽 밖으로 나갈 수는 없다. 즉 $0$번 구간에 있으면 반드시 오른쪽으로, $N-1$번 구간에 있으면 반드시 왼쪽으로 이동한다.

• $2 \le N \le 1000$
• $0 \le P \le Q \le N-1$
• $0 \le J \le N-1$
• $1 \le K \le 60$
• 테스트 케이스는 100개 이하이다.
• 마지막 줄은 항상 0 0 0 0 0이다.

각 테스트 케이스마다 $K$번 이동한 뒤 안전 구간에 서 있게 되는 이동 방법의 수를 한 줄에 하나씩 출력한다. 답은 64비트 부호 있는 정수 범위에 들어간다.