eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Детский магазин

Детский магазин

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

В детский магазин завезли n одинаковых кубиков. Для поддержания разнообразия ассортимента руководство магазина решило сделать их разноцветными. Имеется возможность раскрасить кубики в k различных цветов, причём не обязательно использовать все цвета.

Определите по числам n и k сколько существует вариантов раскраски (различными считаются варианты, в которых отличается количество кубиков хотя бы одного цвета).

Входные данные

В первой строке входного файла задано количество тестов t (1t10). Каждый тест состоит из одной строки, содержащей через пробел n и k (1n, k10^18).

Выходные данные

Для каждого теста выведите строку, содержащий ответ к задаче. Так как ответ может быть достаточно большим, выведите его по модулю 1000000007 (10^9+7).

Пример

Входные данные #1
3
3 1
3 2
5 2
Выходные данные #1
1
4
6
Автор Евгений Служаев