Olenka lentdəki naxış üçün ştamp hazırlayır. Ştamp — hər biri rəngdən birinə boyanmış xanadan ibarət zolaqdır. Xanaların rənglərini soldan sağa w_1, w_2, \ldots, w_n (1 \le w_i \le k) ilə işarə edək.
Lentdəki izləri bir-birinə qarışdırmaq mümkün olmasın deyə, Olenkaya uğurlu ştamp lazımdır. Ştamp uğurlu adlanır, əgər onun heç bir prefiksi eyni uzunluqlu suffiksi ilə eyni şəkildə boyanmayıbsa. Yəni -dən n - 1-ə qədər hər bir üçün ilk xana son xanadan fərqlənir:
Bir xanadan ibarət ştamp həmişə uğurludur.
Məsələn, k = 3 olduqda , və ştampları uğurludur, (l = 1), (l = 2) və (l = 1, 2, 3) ştampları isə yox.
Sizə sorğu verilir. Hər sorğu üçün rəngə boyanmış xanadan ibarət uğurlu ştampların sayını hesablayın. Cavablar çox böyük ola bildiyi üçün onları 10^9 + 7 moduluna görə çıxarın.
Birinci sətirdə bir tam ədəd (1 \le t \le 10^5) — sorğuların sayı verilir.
Sonrakı sətirdən hər biri iki tam ədəd və (1 \le n \le 10^6, 1 \le k \le 10^9) — ştampın xanalarının sayı və rənglərin sayı ehtiva edir.
Bütün sorğular üzrə qiymətlərinin cəminin 10^6-dan çox olmadığı təmin edilir.
Hər sorğu üçün ayrıca sətirdə rəngə boyanmış xanadan ibarət uğurlu ştampların sayını 10^9 + 7 moduluna görə çıxarın.
Nümunə 1
Nümunə 2
Birinci nümunədə:
n = 1 üçün hər ştamp uğurludur.
n = 2, k = 3 üçün ştamp yalnız və yalnız onun iki xanası müxtəlif rəngdə olduqda uğurludur: 3 \cdot 2 = 6 ştamp.
n = 3, k = 2 üçün uğurlu ştamplar , , və -dir.
n = 4, k = 2 üçün uğurlu ştamplar , , , , və -dir. Məsələn, ştampı uğurlu deyil, çünki onun ilk iki xanası son iki xanası ilə eyni şəkildə boyanıb, ştampı isə uğurlu deyil, çünki o, rəngi ilə başlayır və bitir.