Суми циклічних сегментів#12885

Суми циклічних сегментів

1 секунда
256 мегабайтів
Складна

Вам дано два цілих числа (2 \le k < n).

Для масиву a_1, a_2, \ldots, a_n, який складається лише з нулів та одиниць, ми визначаємо масив наступним чином:

Розглянемо всі 2^n можливих масивів і для кожного з них знайдемо . Скільки серед них різних масивів? Оскільки відповідь може бути дуже великою, виведіть кількість цих масивів за модулем .

Два масиви вважаються різними, якщо вони відрізняються хоча б однією позицією.

Вхідні дані

Перший рядок містить одне ціле число (1 \le t \le 10^5)  — кількість тестів. Нижче наведено опис тестових випадків.

Перший рядок кожного тесту містить два цілих числа (2 \le k < n \le 10^6).

Вихідні дані

Для кожного тесту виведіть кількість різних масивів серед за модулем .

Приклади

Приклад 1

Loading
Loading

Примітка

Для n = 3, k = 2 існує різних масивів одиниць і нулів. Відповідні масиви для них попарно різні.

Для n = 4, k = 2 існує різних масивів одиниць і нулів. Єдиною парою відповідних масивів є [0, 1, 0, 1] і [1, 0, 1, 0]: для обох масивів є [1 , 1, 1, 1].