Складні підйоми

Обмеження: 2 сек., 256 МіБ

Сьогодні Зеник з Марічкою підкорили \(n\) вершин у Карпатах. Зеник має старий гірський довідник, де складність підйому для кожної вершини позначають цілим додатним числом, що не перевищує \(k\). Зауважте, що різні вершини можуть мати однакову складність.

На кожній вершині під час відпочинку наші герої рахували кількість вершин, які вони відвідали до цього зі складністю не більшою ніж у тої, де вони зараз знаходяться. Потім цю кількість Зеник записував у свій зошит.

Ввечері, зручно розмістившись у наметі, Марічка у прямому етері хизується перед подругами своїми гірськими пригодами. Вона розповідає про те наскільки цікаво і водночас складно було долати карпатські маршрути. Аби підтвердити свої слова, Марічка демонструє записи у зошиті Зеника, а подруги намагаються зрозуміти наскільки складними були підйоми. Проте відновити послідовність складностей підйомів на основі записів Зеника не так вже й просто. Ба більше, таких послідовностей може бути декілька, або ж жодної, якщо Зеник помилився. Допоможіть Марічці знайти кількість таких послідовностей, що відповідають записаній інформації.

Вхідні дані

Перший рядок містить через пробіл два цілих числа \(n\) та \(k\). У другому рядку задані \(n\) цілих чисел через пробіл \(c_1, \ldots, c_n\) — записи у зошиті Зеника.

Вихідні дані

Кількість різних послідовностей, що відповідають записам Зеника, за модулем \(10^9+7\).

Обмеження

\(1 \le n, k \le 10^5\),

\(0 \le c_i < n\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 3 0 1 2 1	5

Примітки

Для прикладу наступні послідовності складностей підйому відповідають записам Зеника:

• 1 2 2 1

• 1 2 3 1

• 1 3 3 1

• 1 3 3 2

• 2 3 3 2