Веселий рахунок не веселий#12383
Вам дано два цілі числа та . Початковий масив складається з [1, 2, 3, \dots, n].
Поки довжина масиву є принаймні , ви виконуєте наступний процес:
Виберіть будь-який неперервний підмасив довжини точно .
Видаліть цей підмасив з .
Об'єднайте залишені ліву та праву частини, щоб утворити новий масив .
Процес завершується, коли |A| < k.
Визначте кількість різних масивів, які можуть існувати, коли процес зупиняється. Оскільки кількість може бути великою, виведіть результат за модулем .
Перший рядок містить ціле число (1 \le T \le 10^6) — кількість тестових випадків.
Кожен з наступних рядків містить два цілі числа, розділені пробілом, та (1 \le n, k \le 10^6).
Для кожного тестового випадку виведіть одне ціле число, що представляє кількість різних термінальних масивів за модулем .
Приклад 1
Підзадача ( балів): 1 \le n, k \le 10.
Підзадача ( балів): \sum n \cdot k \le 10^6 для всіх тестових випадків.
Підзадача ( балів): \sum n \le 10^6 для всіх тестових випадків.
Підзадача ( балів): однаковий для всіх тестових випадків.
Підзадача ( балів): Без додаткових обмежень.