Codeforces Round 274 (Div. 2) |
---|
Закончено |
Представьте себе, что вы находитесь в здании, в котором есть ровно 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.
Пояснения к примерам:
Название |
---|