Анти palindromik sətirlər

Verilmiş iki ədəd n və m. Uzunluğu n olan və simvolları ölçüsü m olan əlifbaya aid olan, uzunluğu birdən böyük olan palindromları alt sırada saxlamayan sətirlərin sayını hesablayın.

Giriş məlumatları

Birinci sətirdə tam ədəd t - testlərin sayı verilir. Sonra testlər gəlir. Hər bir test iki tam ədəd n və m (1 ≤ n, m ≤ 10^9) olan bir sətirdən ibarətdir.

Çıxış məlumatları

Hər bir test üçün tələb olunan sayını 10^9 + 7 moduluna görə çıxarın.

Nümunələr