You are given two integers, \(N\) and \(M\). Count the number of strings of length \(N\) (under the alphabet set of size \(M\)) that doesn't contain any palindromic string of the length greater than \(1\) 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, \(T\), the number of test cases.
Then there will be \(T\) lines, each containing two space-separated integers, \(N\) and \(M\), denoting a single test case. The meanings of \(N\) and \(M\) 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 \(10^9+7\)
Constraints
- \(1\leq T\leq 10^5\)
- \(1\leq N,M\leq 10^9\)
Sample Input
2
2 2
2 3Sample Output
2
6Solution
Lets analyse the problem inductive.
Case \(N=1\):
Since no palindromes of length \(>1\) are allowed, all possible characters can be used, resulting in \(M\) combinations:
\[\Gamma(M, N):= M\]
Case \(N=2\):
Since palindromes can be formed only as \(AA\), \(BB\), \(CC\) and so on, the second character must be different from the first, which reduces the number of possible characters for the second place by one:
\[\Gamma(M, N):= M\cdot(M - 1)\]
Case \(N=3\):
Since we can choose any character for the third place except the two before, the number of possibilities is reduced by one again:
\[\Gamma(M, N):= M\cdot(M - 1)\cdot(M - 2)\]
Lets take the example with \(M=3\): AAA, AAB, AAC, ABA, ABB, ACA, ACC, BAA, BAB, BBA, BBB, BBC, BBB, BCB, CAA, CAC, CBB, CBC, CCA, CCB and CCC have all a palindromic pattern, while ABC, ACB, BAC, BCA, CAB and CBA are anipaledrome. Which demonstrates the reasoning behind the derived formula.
Case \(N>3\):
Since we are looking for strings that do not contain any palindromic consecutive substrings, it is sufficient to exclude two and three-digit palindromes, since all longer palindromes contain them anyway. That is
\[\Gamma(M, N):= M\cdot(M - 1)\cdot(M - 2)^{N - 2}\]
Plugging cases \(N\in\{1, 2, 3\}\) into the general formula for the last case reveals
- \(N=1: M\cdot(M - 1)\cdot(M - 2)^{1 - 2}\neq M\)
- \(N=2: M\cdot(M - 1)\cdot(M - 2)^{2 - 2} = M\cdot(M - 1)\)
- \(N=3: M\cdot(M - 1)\cdot(M - 2)^{3 - 2} = M\cdot(M - 1)\cdot(M - 2)\)
This is interesting! This suggests that Case \(N>3\) really is \(N>1\)! Using Python with its modular exponentiation capabilities of the pow function makes it easy to implement:
def solve(n, m):
q = 1000000007
if n == 1:
return m % q
return (m * (m - 1) * pow(m - 2, n - 2, q)) % q