Anti-Palindromic Strings(number of non palindromic string of length n formed with M types of character)

Anti-Palindromic Strings

You are given two integers,  and . Count the number of strings of length  (under the alphabet set of size ) that doesn't contain any palindromic string of the length greater than  as a consecutive substring.

Input Format

Several test cases will be given to you in a single file. The first line of the input will contain a single integer, , the number of test cases.

Then there will be  lines, each containing two space-separated integers,  and , denoting a single test case. The meanings of  and  are described in the Problem Statement above.

Output Format

For each test case, output a single integer - the answer to the corresponding test case. This number can be huge, so output it modulo .

Constraints

Sample Input

2
2 2
2 3

Sample Output

2
6

Explanation

For the 1st testcase, we have an alphabet of size M = 2. For the sake of simplicity, let's consider the alphabet as [A, B]. We can construct four strings of size N = 2 using these letters.

AA
AB
BA
BB

Out of these, we have two strings, AB and BA, that satisfy the condition of not having a palindromic string of length greater than 1. Hence, the answer 2.

For the 2nd test case, we have an alphabet of size M = 3. For the sake of simplicity, let's consider the alphabet as [A, B, C]. We can construct nine strings of size N = 2 using these letters.

AA
AB
AC
BA
BB
BC
CA
CB
CC

Save AA, BB, and CC, all the strings satisfy the given condition; hence, the answer 6.

=========================editorial=============================

First we have to realize that the anti-palindromic string is a string that does not contain any palindromic substrings of the length of  and , because all the palindromic strings of the greater lengths contain at least one palindromic substring of the length of  or  - basically in the center.

So, the following is true:

• There are  ways to choose the first symbol of the string;
• Then there are  ways to choose the second symbol of the string - basically it should not be equal to the first one;
• Then there are  ways to choose any next symbol - basically it should not coincide with the previous symbols, that aren't equal.

Knowing this, we can write the answer in the following ways:

• If , then the answer is ;
• If , then the answer is ;
• If , then the answer is .since if we are filling 4th character in (m-2) ways which means it is not similar with character at index 1,2 so (1,2,3) is not a palindrom ,similarly (2,3,4) will be not a palindrom and one main observation is that if a string dont have palindrom of length 2,3 than it can have palindrom of length >3
• 
  

For finding  you can use binary exponentiation.