Отслеживание поездов 2
Ежедневно мимо фермы проходит экспресс. Он имеет n вагонов, каждый из которых пронумерован натуральным числом от 1 до 10^9, разные вагоны могут иметь одинаковый номер.
Обычно Бесси наблюдает за поездом, отслеживая номера вагонов. Но сегодня слишком туманно, и Бесси не видит их! К счастью, она приобрела минимумы скользящего окна последовательностей номеров вагонов из авторитетного источника в городе. В частности, у нее имеется натуральное число k и n - k + 1 натуральных чисел c[1],..., c[n] + 1 − k, где c[i] - это минимальный номер среди вагонов i, i + 1,..., i + k − 1.
Помогите Бесси вычислить количество способов присвоить номера каждому вагону в соответствии с минимумами скользящего окна. Поскольку это число может быть очень большим, Бесси хочет найти его остаток по модулю 10^9 + 7.
Информация Бесси полностью достоверна, то есть гарантировано существует по крайней мере один способ присвоения номеров.
Входные данные
Первая строка состоит из двух целых чисел n (1 ≤ n ≤ 10^5) и k. Последующие строки содержат минимумы скользящего окна c[1], ..., c[n] + 1 − k, по одному в строке.
Выходные данные
Выведите одно целое число: количество способов (по модулю 10^9 + 7) присвоить каждому вагону натуральное число, не превышающее 10^9 так, что минимальный номер среди вагонов i, i + 1, ..., i + k − 1 равен c[i] для каждого 1 ≤ i ≤ n − k + 1.