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:
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.
İ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.
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.
Örnek 1
Örnek 2
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.