This year IFEST team thought of introducing a new game which is similar to the famous skipping stones game in Takeshi’s castle but which a slight modification. For that ifest team need your help.
There are N floating stones. Let us number the stones from left to right from 1 to N. Unfortunately one of the stones numbered b broke and hence you can never jump on to it.
You initially start your game from stone numbered a. You will be given k turns and in each turn you jump on to the stone other than the one you are on, but with a condition. That is, your jumping radius during the start of each turn is limited to the difference between current stone number you are on (let’s say X) and the broken stone b, i.e. mathematically |x-y|<|x-b|. Where Y is the stone you want to jump onto to. So your task is to find out how many such distinct sequences of stones you could have stepped on to in your given k turns.
As the result can be large, output the value mod 1000000007(10^9+7).
Input
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 number of sequences by 1000000007 (10^9?+?7).
There are 5 stones.Initially we are on stone number 2 i.e a = 2 ,and b is 4 .So on 1st turn we can jump to either stone number 3 or on stone number 1 . So at the end of 1st turn you have sequences (2 , 3) and (2 ,1). So at the end of 1st turn you have 2 sequences.