Представьте себе, что вы находитесь в здании, в котором есть ровно 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).
Примечание
Две последовательности p1, p2, ..., pk и q1, q2, ..., qk называются различными, если существует такое целое число j (1 ≤ j ≤ k), что pj ≠ qj.
Пояснения к примерам:
- В первом примере после первой поездки вы можете оказаться либо на этаже 1, либо на этаже 3, поскольку |1 - 2| < |2 - 4| и |3 - 2| < |2 - 4|.
- Во втором примере всего две возможных последовательности: (1, 2); (1, 3). Вы не можете выбрать этаж 3 для первой поездки, потому что в этом случае никакой из этажей не подойдет для второй поездки.
- В третьем примере искомых последовательностей не существует, поскольку вы не можете выбрать этаж для первой поездки.