- Prepare
- Mathematics
- Combinatorics
- Anti-Palindromic Strings

# Anti-Palindromic Strings

# 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 *1 ^{st}* 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 *2 ^{nd}* 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`

.