Anti-palindromic strings#9616
Given two integers and , compute the number of strings of length over an alphabet of size that do not contain any substring which is a palindrome of length greater than one.
The first line contains the number of test cases . Each test case consists of a single line containing two integers and m~(1 \le n, m \le 10^9).
For each test case, print the required number of strings modulo 10^9 + 7.
Example 1