Відстеження поїздів 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.