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

Limits: 2 sec., 256 MiB

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

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

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

Input

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

Output

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

Constraints

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

\(0 \le c_i < n\).

Samples

Input (stdin) сopy	Output (stdout) сopy
4 3 0 1 2 1	5

Notes

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

• 1 2 2 1

• 1 2 3 1

• 1 3 3 1

• 1 3 3 2

• 2 3 3 2