Ежедневно мимо фермы проходит экспресс. Он имеет 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.