У детячий магазин завезли \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}).