Competitions

# April 16 Contest

# Anti-palindromic strings

Two integers **n** and **m** are given. Find the number of strings of length **n**, which symbols belong to the alphabet of size **m**, that do not contain palindromes of length more than one as substrings.

#### Input

First line contains the number of test cases **t**. Each test is a separate line with two integers **n** and **m** (**1** ≤ **n**, **m** ≤ `10`

).^{9}

#### Output

For each test case print in a separate line the required number of strings taken by modulo `10`

+ ^{9}**7**.

Input example #1

2 5 6 6 5

Output example #1

1920 1620

Input example #2

4 3 6 1 3 3 1 2 4

Output example #2

120 3 0 12