CodeforcesRound#274(Div.2)E.RidinginaLift（DP）_html/css_WEB-ITnose

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|?

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

5 2 4 1

output

input

5 2 4 2

output

input

5 3 4 1

output

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

思路：比较容易想到的是dp[i][j]表示第i次到了j层的可能，分情况讨论，例如：当a

#include #include #include #include #include using namespace std;const int mod = 1000000007;const int maxn = 5005;int n, a, b, k, dp[maxn][maxn];int sum[maxn];int main() {	scanf("%d%d%d%d", &n, &a, &b, &k);		memset(dp, 0, sizeof(dp));	if (a < b) {		dp[0][a] = 1;		for (int j = 1; j < b; j++)			sum[j] = sum[j-1] + dp[0][j];		for (int i = 1; i <= k; i++) {			for (int j = 1; j < b; j++)				dp[i][j] = (sum[(b-j-1)/2+j] - dp[i-1][j] + mod) % mod;			sum[0] = 0;			for (int j = 1; j < b; j++)				sum[j] = (sum[j-1] + dp[i][j]) % mod;		}		printf("%d\n", sum[b-1]);	}	else {		dp[0][a] = 1;		for (int j = n; j >= b+1; j--)			sum[j] = sum[j+1] + dp[0][j];		for (int i = 1; i <= k; i++) {			for (int j = b+1; j <= n; j++) 				dp[i][j] = (sum[j-(j-b-1)/2] - dp[i-1][j] + mod) % mod;			sum[0] = 0;			for (int j = n; j >= b+1; j--)				sum[j] = (sum[j+1] + dp[i][j]) % mod;		}		printf("%d\n", sum[b+1]);	}	return 0;}