E. Катаемся на лифте
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Представьте себе, что вы находитесь в здании, в котором есть ровно n этажей. Для перемещения между этажами в здании есть лифт.

Пронумеруем этажи снизу вверх целыми числами от 1 до n. Сейчас вы находитесь на этаже с номером a. Вам очень скучно, поэтому вы хотите покататься на лифте. На этаже с номером b находится секретная лаборатория, вход в которую вам запрещен. Однако вы уже настроились и решили последовательно совершить k поездок на лифте.

Предположим, что в данный момент вы находитесь на этаже с номером x (изначально вы находились на этаже a). Для очередной поездки между этажами вы выбираете некоторый этаж с номером y (y ≠ x), и лифт везет вас на этот этаж. Поскольку вам нельзя посещать этаж b с секретной лабораторией, то вы решили, что расстояние от текущего этажа x до выбранного этажа y должно быть строго меньше, чем расстояние от текущего этажа x до этажа b с секретной лабораторией. Формально, это означает, что должно выполняться неравенство |x - y| < |x - b|. После того, как лифт успешно привез вас на этаж y, вы выписываете себе в блокнот число y.

Ваша задача — определить количество различных последовательностей чисел, которые вы могли выписать себе в блокнот в результате k поездок на лифте. Поскольку искомое количество может быть очень большим, найдите остаток от деления этого количества на 1000000007 (109 + 7).

Входные данные

В первой строке входных данных записаны четыре целых положительных числа через пробел n, a, b, k (2 ≤ n ≤ 5000, 1 ≤ k ≤ 5000, 1 ≤ a, b ≤ n, a ≠ b).

Выходные данные

Выведите единственное число — остаток от деления искомого количества последовательностей на 1000000007 (109 + 7).

Примеры
Входные данные
5 2 4 1
Выходные данные
2
Входные данные
5 2 4 2
Выходные данные
2
Входные данные
5 3 4 1
Выходные данные
0
Примечание

Две последовательности p1, p2, ..., pk и q1, q2, ..., qk называются различными, если существует такое целое число j (1 ≤ j ≤ k), что pj ≠ qj.

Пояснения к примерам:

  1. В первом примере после первой поездки вы можете оказаться либо на этаже 1, либо на этаже 3, поскольку |1 - 2| < |2 - 4| и |3 - 2| < |2 - 4|.
  2. Во втором примере всего две возможных последовательности: (1, 2); (1, 3). Вы не можете выбрать этаж 3 для первой поездки, потому что в этом случае никакой из этажей не подойдет для второй поездки.
  3. В третьем примере искомых последовательностей не существует, поскольку вы не можете выбрать этаж для первой поездки.