Safe Zone

Saruman's army has laid siege to Helm's Deep and is firing volley after volley of arrows at its walls. The Rohirrim have shields for only one stretch of the wall. You are a soldier in King Theoden's army, and you have to reach that stretch before the next volley lands.

From left to right the wall segments are numbered $0$ through $N-1$, and you are standing on segment $J$. The shields cover segments $P$ through $Q$. Before the next volley you have time for exactly $K$ steps, and each step moves you one segment left or one segment right. The wall shakes too hard for you to stand still.

Count the sequences of $K$ steps that leave you on a segment between $P$ and $Q$. Two sequences that differ in any step are counted separately.

The input holds several test cases. Each test case is one line with $N$, $P$, $Q$, $J$, and $K$ separated by spaces. $N$ is the length of the wall, $P$ and $Q$ are the ends of the safe zone, $J$ is the starting position, and $K$ is the number of steps. A line whose $N$ is $0$ marks the end of the input and produces no output.

You cannot walk off the end of the wall. On segment $0$ you must step right, and on segment $N-1$ you must step left.

• $2 \le N \le 1000$
• $0 \le P \le Q \le N-1$
• $0 \le J \le N-1$
• $1 \le K \le 60$
• There are at most 100 test cases.
• The last line is always 0 0 0 0 0.

For each test case, print on its own line the number of ways to end up in the safe zone after $K$ steps. The answer fits in a signed 64-bit integer.