Naxış#13075

Naxış

1 saniyə
256 meqabayt

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:

w_1 w_2 \ldots w_l \ne w_{n-l+1} w_{n-l+2} \ldots w_n.

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.

Giriş

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.

Çıxış

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ələr

Nümunə 1

Loading
Loading

Nümunə 2

Loading
Loading

Qeyd

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.