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

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