Uşaq mağazası#3238
Uşaq mağazasına n ədəd eyni kubik gətirilib. Mağaza rəhbərliyi çeşidin müxtəlifliyini təmin etmək üçün bu kubikləri müxtəlif rənglərə boyamağa qərar verib. Kubikləri k fərqli rəngdə boyamaq mümkündür, lakin bütün rənglərdən istifadə etmək məcburi deyil.
Verilən n və k ədədlərinə əsasən, neçə fərqli boyama variantının olduğunu müəyyən edin (fərqli sayılan variantlar, ən azı bir rəngdə olan kubiklərin sayının fərqli olduğu variantlardır).
Giriş faylının birinci sətirində testlərin sayı t (1 ≤ t ≤ 10) verilib. Hər bir test bir sətirdən ibarətdir və boşluqla ayrılmış n və k (1 ≤ n, k ≤ 10^18) ədədlərini ehtiva edir.
Hər bir test üçün məsələnin cavabını ehtiva edən bir sətir çıxarın. Cavab kifayət qədər böyük ola biləcəyi üçün onu 1000000007 (10^9+7) moduluna görə çıxarın.
Nümunə 1