Дитячий магазин

У детячий магазин завезли n однакових кубиків. Для підтримки різноманіття асортименту керівнництво магазину вирішило зробити їх різнокольоровими. Є можливість розфарбувати кубики у k різних кольорів, причому не обов'язково використовувати усі кольори.

Визначте за числам n та k скільки існує варіантів розфарбування (різними вважаються варіанти, у яких відрізняється кількість кубиків хоча б одного кольору).

Вхідні дані

У першому рядку вхідного файлу задано кількість тестів t (1 ≤ t ≤ 10). Кожен тест складається з одного рядка, який містить відокремлені пропуском n та k (1 ≤ n, k ≤ 10^18).

Вихідні дані

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

Приклади