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 ≤ 109).

Output

For each test case print in a separate line the required number of strings taken by modulo 109 + 7.