Desen#13075

Desen

1 saniye
256 megabayt

Olenka bir kurdele üzerindeki desen için damga yapıyor. Damga, her biri renkten birine boyanmış hücreden oluşan bir şerittir. Hücrelerin renklerini soldan sağa w_1, w_2, \ldots, w_n (1 \le w_i \le k) ile gösterelim.

Kurdele üzerindeki izlerin birbirine karıştırılamaması için Olenka'nın başarılı bir damgaya ihtiyacı var. Bir damga, hiçbir öneki kendisiyle aynı uzunluktaki soneki ile aynı şekilde boyanmamışsa başarılı olarak adlandırılır. Yani 'den n - 1'e kadar her için ilk hücre son hücreden farklıdır:

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

Tek bir hücreden oluşan damga her zaman başarılıdır.

Örneğin, k = 3 için , ve damgaları başarılıdır, buna karşın (l = 1), (l = 2) ve (l = 1, 2, 3) damgaları başarılı değildir.

Size sorgu veriliyor. Her sorgu için renge boyanmış hücreden oluşan başarılı damgaların sayısını bulun. Cevaplar çok büyük olabileceğinden, onları 10^9 + 7 moduna göre yazdırın.

Giriş

İlk satırda bir tam sayı (1 \le t \le 10^5) — sorgu sayısı verilir.

Sonraki satırın her biri iki tam sayı ve (1 \le n \le 10^6, 1 \le k \le 10^9) — damganın hücre sayısı ve renk sayısı içerir.

Tüm sorgular boyunca değerlerinin toplamının 10^6'yı aşmadığı garanti edilir.

Çıktı

Her sorgu için ayrı bir satırda, renge boyanmış hücreden oluşan başarılı damgaların sayısını 10^9 + 7 moduna göre yazdırın.

Örnekler

Örnek 1

Loading
Loading

Örnek 2

Loading
Loading

Not

Birinci örnekte:

  • n = 1 için damganın hepsi başarılıdır.

  • n = 2, k = 3 için bir damga ancak ve ancak iki hücresi farklı renklerde olduğunda başarılıdır: 3 \cdot 2 = 6 damga.

  • n = 3, k = 2 için başarılı damgalar , , ve 'dir.

  • n = 4, k = 2 için başarılı damgalar , , , , ve 'dir. Örneğin, damgası başarılı değildir, çünkü ilk iki hücresi son iki hücresiyle aynı şekilde boyanmıştır; damgası da başarılı değildir, çünkü rengiyle başlayıp rengiyle biter.