小G 来到了著名的CIGOM 大厦。大厦一共有n 层,初始的时候小G 在第A
层。小G 特别想去B 层小M 的办公室看一看,然而因为安保原因,B 层已经被
封锁无法进入。
但是小G 既然来了,就想在大厦里面逛一逛。大厦里面有一部电梯,小G 决
定坐k 次电梯。因为小G 比较无聊,他给自己设定了这样一个规矩:假如当前他
在x 层,则他要去的下一个楼层y 和x 的楼层差必须要小于x 和B 的楼层差。每到达一个楼层,小G 都要记录下来其楼层号。
当小G 转完一圈后,他也记录下了k +1 个楼层号(可能有重复)。小G 现在想知道,按照他定下的规矩,一共有多少种可能的楼层号序列?
输入格式
输入文件一行,4 个数字n; A;B; k,含义如题目所述。
输出格式
输出一个数字,表示可能的楼层号序列的数量。答案对109 + 7 取模。
样例输入
5 2 4 1
样例输出
2