Antipalindromik sətrlər#9616
Verilmiş iki tam ədəd və . Gücü olan əlifbanın simvollarından tərtib olunmuş uzunluğu olan sətrlər içərisində uzunluğu birdən böyük palindrom olan heç bir alt sətri olmayan sətrlərin sayını hesablayın.
Birinci sətirdə testlərin sayı verilir. Hər bir test bir sətirdən ibarətdir, burada iki tam ədəd və m~(1 \le n, m \le 10^9) verilmişdir.
Hər bir test üçün axtarılan sətrlərin sayını 10^9 + 7 modulu ilə çıxarın.
Nümunə 1