В детский магазин завезли \textbf{n} одинаковых кубиков. Для поддержания разнообразия ассортимента руководство магазина решило сделать их разноцветными. Имеется возможность раскрасить кубики в \textbf{k} различных цветов, причём не обязательно использовать все цвета. Определите по числам \textbf{n} и \textbf{k} сколько существует вариантов раскраски (различными считаются варианты, в которых отличается количество кубиков хотя бы одного цвета). \InputFile В первой строке входного файла задано количество тестов \textbf{t} (\textbf{1} ≤ \textbf{t} ≤ \textbf{10}). Каждый тест состоит из одной строки, содержащей через пробел \textbf{n} и \textbf{k} (\textbf{1} ≤ \textbf{n}, \textbf{k} ≤ \textbf{10^18}). \OutputFile Для каждого теста выведите строку, содержащий ответ к задаче. Так как ответ может быть достаточно большим, выведите его по модулю \textbf{1000000007} (\textbf{10^9+7}).