Imagine that you are in a building that has exactly n floors. You can move between the floors in a lift. Let's number the floors from bottom to top with integers from 1 to n. Now you're on the floor number a. You are very bored, so you want to take the lift. Floor number b has a secret lab, the entry is forbidden. However, you already are in the mood and decide to make k consecutive trips in the lift.
Let us suppose that at the moment you are on the floor number x (initially, you were on floor a). For another trip between floors you choose some floor with number y (y≠x) and the lift travels to this floor. As you cannot visit floor b with the secret lab, you decided that the distance from the current floor x to the chosen y must be strictly less than the distance from the current floor x to floor b with the secret lab. Formally, it means that the following inequation must fulfill: |x-y|<|x-b|. After the lift successfully transports you to floor y, you write down number y in your notepad.
Your task is to find the number of distinct number sequences that you could have written in the notebook as the result of k trips in the lift. As the sought number of trips can be rather large, find the remainder after dividing the number by 1000000007 (109+7).
The first line of the input contains four space-separated integers n, a, b, k (2≤n≤5000, 1≤k≤5000, 1≤a,b≤n, a≠b).
Print a single integer − the remainder after dividing the sought number of sequences by 1000000007 (109+7).
5 2 4 1
2
5 2 4 2
2
5 3 4 1
0
Two sequences p1,p2,...,pk and q1,q2,...,qk are distinct, if there is such integer j (1≤j≤k), that pj≠qj.
Notes to the samples: