Problem 5758. -- 小G坐电梯

5758: 小G坐电梯

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 8  Solved: 2
[Submit][Status][Web Board]

Description

小 G 来到了著名的 CIGOM 大厦。大厦一共有 n 层,初始的时候小 G 在第 A层。小 G 特别想去 B 层小 M 的办
公室看一看,然而因为安保原因,B 层已经被封锁无法进入。但是小 G 既然来了,就想在大厦里面逛一逛。大厦
里面有一部电梯,小 G 决定坐 k 次电梯。因为小 G 比较无聊,他给自己设定了这样一个规矩:假如当前他在 x 
层,则他要去的下一个楼层 y 和 x 的楼层差必须要小于 x 和 B 的楼层差,即|x - y| < |x - B|。每到达一个
楼层,小 G 都要记录下来其楼层号。当小 G 转完一圈后,他也记录下了 k + 1 个楼层号(可能有重复)。小 G 
现在想知道,按照他定下的规矩,一共有多少种可能的楼层号序列?

Input

输入文件一行,4 个数字 n, A, B, k,含义如题目所述。
2 ≤ n ≤ 5000, 1 ≤ k ≤ 5000, 1 ≤ A, B ≤ n, A != B。

Output

输出一个数字,表示可能的楼层号序列的数量。答案对 10^9 + 7 取模。

Sample Input

5 2 4 1

Sample Output

2

HINT

Source

[Submit][Status]