Codeforces Round #274 (Div. 2) E. Riding in a Lift（DP）

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).

Input

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).

Output

Print a single integer — the remainder after dividing the sought number of sequences by 1000000007 (109 + 7).

Sample test(s)

input

output

题意：做电梯，刚開始的时候你在a层，不能到b层。每次你到新的地方的y，必须满足|x-y|<|x-b|，求坐k次有多少种可能

思路：比較easy想到的是dp[i][j]表示第i次到了j层的可能，分情况讨论。比如：当a<b的时候，下一次的层数i是不能超过j+(b-j-1)/2的。然后每次预先处理出前j层的可能。

本文转自mfrbuaa博客园博客，原文链接：http://www.cnblogs.com/mfrbuaa/p/5261360.html，如需转载请自行联系原作者