Отслеживание поездов 2
Отслеживание поездов 2
Ежедневно мимо фермы проходит экспресс. Он имеет n вагонов, каждый из которых пронумерован натуральным числом от 1 до 109
, разные вагоны могут иметь одинаковый номер.
Обычно Бесси наблюдает за поездом, отслеживая номера вагонов. Но сегодня слишком туманно, и Бесси не видит их! К счастью, она приобрела минимумы скользящего окна последовательностей номеров вагонов из авторитетного источника в городе. В частности, у нее имеется натуральное число k и n - k + 1 натуральных чисел c1
,..., cn
+ 1 − k, где ci
- это минимальный номер среди вагонов i, i + 1,..., i + k − 1.
Помогите Бесси вычислить количество способов присвоить номера каждому вагону в соответствии с минимумами скользящего окна. Поскольку это число может быть очень большим, Бесси хочет найти его остаток по модулю 109
+ 7.
Информация Бесси полностью достоверна, то есть гарантировано существует по крайней мере один способ присвоения номеров.
Входные данные
Первая строка состоит из двух целых чисел n (1 ≤ n ≤ 105
) и k. Последующие строки содержат минимумы скользящего окна c1
, ..., cn
+ 1 − k, по одному в строке.
Выходные данные
Выведите одно целое число: количество способов (по модулю 109
+ 7) присвоить каждому вагону натуральное число, не превышающее 109
так, что минимальный номер среди вагонов i, i + 1, ..., i + k − 1 равен ci
для каждого 1 ≤ i ≤ n − k + 1.
4 2 999999998 999999999 999999998
3