Задачи
Детский магазин
Детский магазин
В детский магазин завезли n одинаковых кубиков. Для поддержания разнообразия ассортимента руководство магазина решило сделать их разноцветными. Имеется возможность раскрасить кубики в k различных цветов, причём не обязательно использовать все цвета.
Определите по числам n и k сколько существует вариантов раскраски (различными считаются варианты, в которых отличается количество кубиков хотя бы одного цвета).
Входные данные
В первой строке входного файла задано количество тестов t (1 ≤ t ≤ 10). Каждый тест состоит из одной строки, содержащей через пробел n и k (1 ≤ n, k ≤ 10^18).
Выходные данные
Для каждого теста выведите строку, содержащий ответ к задаче. Так как ответ может быть достаточно большим, выведите его по модулю 1000000007 (10^9+7).
Пример
Входные данные #1
3 3 1 3 2 5 2
Выходные данные #1
1 4 6