Гра з кроликом#3403
У грі кролик проходить рівні, кожен з яких має свою складність. Кролик амбітний і зазвичай хоче грати на рівні, що є складнішим за попередній. Однак іноді, щоб відпочити, він дозволяє собі грати на легшому рівні. Але він погоджується грати на рівні тільки якщо його складність не є меншою за складність попереднього більш ніж на одиниць (тобто, різниця між складністю попереднього рівня та наступного не перевищує і не є від'ємною).
Ваше завдання — визначити, скількома способами кролик може пройти всі рівні, дотримуючись цього правила. Оскільки відповідь може бути дуже великою, виведіть її по модулю .
Перший рядок містить два цілих числа і (1 \leq N \leq 100\,000, 1 \leq T \leq 100\,000). Тут — кількість рівнів, а — максимально допустима різниця у складності між рівнями.
Наступні рядків містять по одному цілому числу D_i (1 \leq D_i \leq 100\,000) — складність -го рівня.
Виведіть кількість способів пройти всі рівні по описаному правилу по модулю .
Приклад 1