Треугольник Паскаля на стене
На стене школы в Узгене художники рисуют треугольник Паскаля: в строке n (n = 0, 1, 2, …) стоят числа C(n, 0), C(n, 1), …, C(n, n), где C(n, k) = n! / (k! · (n − k)!). Клетку закрашивают тёмной краской, если её число делится на p^e, где p — простое число. Если покрасить так много строк, на стене проступает фрактал, похожий на треугольник Серпинского.
Строки 0–80, p = 3, e = 1: светлые клетки — числа, не делящиеся на 3.
Художникам нужно знать, сколько тёмной краски купить. Для каждого из T вопросов N p e найдите, сколько среди чисел C(n, k) с 0 ≤ k ≤ n < N (то есть в первых N строках) делятся на p^e. Ответ выведите по модулю 10⁹ + 7.
Входные данные
В первой строке — число T (1 ≤ T ≤ 1000). В каждой из следующих T строк — три целых числа N, p, e (1 ≤ N ≤ 10¹⁸, 2 ≤ p ≤ 10⁹, p — простое, 1 ≤ e ≤ 60).
Выходные данные
Для каждого вопроса выведите в отдельной строке количество чисел, делящихся на p^e, по модулю 10⁹ + 7.
Пример 1
Вход:
4
6 2 1
6 2 2
6 5 1
100 3 2
Выход:
6
2
4
2240
Пояснение
Первые 6 строк треугольника: 1; 1 1; 1 2 1; 1 3 3 1; 1 4 6 4 1; 1 5 10 10 5 1. На 2 делятся шесть чисел: 2, 4, 6, 4, 10, 10; на 4 — два числа (4 и 4); на 5 — четыре числа (5, 10, 10, 5).
Система оценивания
Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 25 % тестов N ≤ 150.
Подсказка
Теорема Куммера: наибольшая степень p, на которую делится C(n, k), равна количеству переносов при сложении чисел k и n − k в системе счисления с основанием p.
Комментарии