Каждый день скоростной поезд проносится мимо фермы. У него имеется
\(N\) вагонов (\(1 \leq N \leq 10^5\)), помеченных положительным целым числом
от 1 до \(10^9\); различные вагоны могут иметь одинаковые метки.
Обычно Беси наблюдает как едет поезд, отслеживая метки вагонов.
Однако сегодня туман, и Беси не видит метки. К счастью, она приобрела
скользящее окно минимумов последовательности меток. В частности,
у неё есть положительное целое число \(K\), и \(N-K+1\) положительных
целых чисел \(c_1,\dots,c_{N+1-K}\), где \(c_i\) - минимальная метка
среди вагонов \(i, i+1, \dots, i+K-1\).
Помогите Беси вычислить количество способов назначить метку каждому вагону
соответствующую показаниям "скользящего окна минимумов". Поскольку
это число может быть очень большим, выведите ответ по модулю \(10^9 + 7\).
Гарантируется, что существует, как минимум, один способ так назначить метки.
ФОРМАТ ВВОДА (файл tracking2.in):
Первая строка содержит два разделённых пробелом целых числа \(N\) и \(K\).
Следующие строки содержать минимумы скользящего окна \(c_1,\dots,c_{N+1-K}\),
по одному в строке.
ФОРМАТ ВЫВОДА (файл tracking2.out):
Одно целое число: количество способов по модулю \(10^9 + 7\), назначить
положительные целые, не превышающие \(10^9\) каждому вагону, так что
минимальная метка среди вагонов \(i, i+1, \dots, i+K-1\) есть \(c_i\) для
всех \(1 \leq i \leq N-K+1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 2
999999998
999999999
999999998
|
3
|