479_E. Riding in a Lift_28646
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).

Examples

Input

5 2 4 1


Output

2


Input

5 2 4 2


Output

2


Input

5 3 4 1


Output

0

Note

Two sequences p1, p2, ..., pk and q1, q2, ..., qk are distinct, if there is such integer j (1 ≤ j ≤ k), that pj ≠ qj.

Notes to the samples:

  1. In the first sample after the first trip you are either on floor 1, or on floor 3, because |1 - 2| < |2 - 4| and |3 - 2| < |2 - 4|. 
  2. In the second sample there are two possible sequences: (1, 2); (1, 3). You cannot choose floor 3 for the first trip because in this case no floor can be the floor for the second trip. 
  3. In the third sample there are no sought sequences, because you cannot choose the floor for the first trip. 
def solve(n, st, k):
    MOD = int(1e9 + 7)
    prev = [0] * (n + 1)
    current = [0] * (n + 1)
    prefix_sum = [0] * (n + 1)
    prev[st] = 1
    for times in range(k):
        prefix_sum[0] = 0
        for i in range(1, n + 1):
            prefix_sum[i] = prefix_sum[i - 1] + prev[i]
            if prefix_sum[i] >= MOD:
                prefix_sum[i] -= MOD
        for i in range(1, n + 1):
            current[i] = prefix_sum[n] - prefix_sum[i >> 1] - prev[i]
            while current[i] < 0: current[i] += MOD
            while current[i] >= MOD: current[i] -= MOD
        prev, current = current, prev
    return sum(prev) % MOD
    

def main():
    n, a, b, k = [int(i) for i in input().split()]
    if a > b:
        print(solve(n - b, a - b, k))
    else:
        print(solve(b - 1, b - a, k))
    
main()

5 3 4 1
 5 2 4 1
 5 2 4 2
 500 1 500 500
 300 300 1 300
 5000 1 5000 5000
 232 195 193 322
 5000 5000 1 5000
 2 2 1 1
 500 499 500 500
 1000 500 1 2000
 3 2 3 1
 300 1 300 300
 500 498 500 499
 500 500 498 5000
 2 1 2 1
 2 1 2 5000
 5000 5000 4999 5000
 5000 2081 3619 5000
 300 299 300 300
 50 5 2 50
 500 500 498 4999
 5000 1 100 3
 100 3 30 5000
 22 9 18 3
 5000 2500 1 5000
 5000 2314 1234 5000
 1000 500 1 1000
 400 11 12 400
 5000 1031 4782 5000
 1000 213 480 1
 4998 2 4 5000
 5000 4998 5000 5000
 5000 1 2500 5000
 2332 2204 558 3722
 50 25 21 50
 2032 1050 1339 2334
 150 150 1 150
 5 1 2 1
 5 3 2 2
 10 1 10 2
 500 436 412 500
 1000 1 500 1000
 222 187 134 500
 100 1 30 500
 50 48 41 2
 10 1 4 4999
 300 300 299 300
 4999 1 2 4999
 5 4 2 1
 5000 100 1 5000
 3999 2 10 5000
 500 498 500 500
 2000 500 1 2000
 443 144 6 223
 4943 944 1747 2213
 4988 3629 4106 4488
 5000 3000 2000 5000
 5000 4999 5000 5000
 5000 2 5000 5000
 232 34 49 234
 488 96 473 488
 10 1 3 4
 5000 1031 4737 5000
 35 9 10 35
 2222 1206 1425 2222
 4999 2500 1 4999
 500 1 500 521
 458 195 193 322
 1000 500 2 2000
 50 5 2 79
 569 500 498 4999
 5000 1 100 5
 22 8 18 3
 5000 3372 1 5000
 5000 697 1234 5000
 1000 500 1 1001
 400 11 12 201
 5000 1196 4782 5000
 1001 213 480 1
 3407 2204 558 3722
 52 25 21 50
 2032 1050 1339 4462
 20 1 10 2
 500 436 412 995
 1000 1 988 1000
 222 208 134 500
 100 1 6 500
 50 48 20 2
 9 1 4 4999
 3999 3 10 5000
 500 498 108 500
 2000 500 1 466
 443 192 6 223
 4943 944 1762 2213
 5000 1345 2000 5000
 5000 1 5000 2189
 232 65 49 234
 840 96 473 488
 35 9 5 35
 4999 2500 2 4999
 458 142 193 322
 1000 120 2 2000
 50 5 2 86
 22 8 18 5
 5000 185 1234 5000
 1000 500 1 1101
 5000 1196 1419 5000
 3407 2204 558 1716
 52 25 5 50
 2032 1050 340 4462
 10 3 2 2
 300 300 299 202
 7 4 2 1
 10 1 3 7
 5 2 1 1
 5 2 1 2
 905 1 500 521
 5000 2 100 5
 400 11 12 108

0
 2
 2
 521515914
 396536590
 233993486
 12938181
 233993486
 0
 0
 744846473
 0
 396536590
 113017568
 0
 0
 0
 0
 557114846
 0
 923222599
 0
 483642
 831733342
 1964
 898026985
 546628648
 921282926
 0
 981271392
 478
 2
 701940824
 968861072
 659576072
 317551605
 439644037
 954984546
 0
 0
 44
 724363905
 594673663
 769809644
 627243445
 44
 2
 0
 0
 2
 363556022
 343196694
 973540182
 288043610
 362569369
 12879261
 349016655
 82819894
 0
 233993486
 984852735
 212471726
 0
 917351304
 0
 402572650
 694314934
 114877708
 457178613
 39612085
 426832774
 944509926
 101594622
 1964
 233993486
 217751851
 350139480
 0
 981271392
 478
 298061514
 888035755
 82018442
 44
 872851446
 342630861
 769809644
 718837056
 616
 2
 343196694
 525373178
 495072669
 498217749
 478886423
 946052176
 372801080
 839027175
 212471726
 770378295
 951312587
 43264982
 632823646
 165562285
 215424
 427443322
 670858217
 659951113
 388222744
 949561472
 211216783
 0
 0
 2
 0
 0
 0
 114877708
 101594622
 0
