Дитячий магазин#3238
У дитячий магазин завезли однакових кубиків. Для підтримки різноманіття асортименту керівництво магазину вирішило зробити їх різнокольоровими. Є можливість розфарбувати кубики у різних кольорів, причому не обов'язково використовувати усі кольори.
Визначте за числами та скільки існує варіантів розфарбування (різними вважаються варіанти, у яких відрізняється кількість кубиків хоча б одного кольору).
У першому рядку вхідного файлу задано кількість тестів (1 \le t \le 10). Кожен тест складається з одного рядка, який містить відокремлені пропуском та (1 \le n, k \le 10^{18}).
Для кожного тесту виведіть рядок, який містить відповідь до задачі. Так як відповідь може бути достатньо великою, виведіть її за модулем (10^9+7).
Приклад 1