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

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

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

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

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

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

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

Примеры