Перестановка картоплі
Обмеження: 2 сек., 256 МіБ
У Марічки в підвалі є багато картоплі. Картопля лежить у мішках, які поскладані в один довгий рядок уздовж стіни. Усього є \(n\) мішків, в \(i\)-ому з них є \(a_i\) картоплин.
Зеник любить переставляти ці мішки. За одну операцію він може взяти два сусідні мішки й поміняти їх місцями, якщо сумарна кількість картоплин у них не перевищує число \(k\). Зеник може виконувати як завгодно багато операцій.
Одного вечора Зенику й Марічці стало цікаво, скільки різних послідовностей мішків Зеник може дістати. Дві послідовності вважаються різними, якщо існує така позиція, що мішки на цій позиції мають різну кількість картоплин.
Вхідні дані
У першому рядку задано два цілих числа \(n\) і \(k\) — кількість мішків та обмеження на мішки, які можна переставляти.
У другому рядку містяться \(n\) цілих чисел \(a_i\) — кількість картоплин в \(i\)-ому мішку.
Вихідні дані
У єдиному рядку виведіть ціле число — остачу від ділення шуканої кількості способів на просте число \(10^9 + 7\).
Обмеження
\(1 \le n \le 10^5\),
\(0 \le k \le 2 \cdot 10^9\),
\(1 \le a_i \le 10^9\).
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
3 7 5 2 4 | 3 |
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
5 4 1 2 3 2 1 | 10 |
Примітки
В першому прикладі можливі комбінації: [5, 2, 4], [2, 5, 4], [5, 4, 2].
Надіслати розв'язок
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|