Olenka is making a stamp for a pattern on a ribbon. A stamp is a strip of cells, each of which is painted in one of colors. Let us denote the colors of the cells from left to right as w_1, w_2, \ldots, w_n (1 \le w_i \le k).
So that the imprints on the ribbon cannot be confused, Olenka needs a successful stamp. A stamp is called successful if no prefix of it is colored the same as the suffix of the same length. That is, for every from to n - 1 the first cells differ from the last :
A stamp consisting of a single cell is always successful.
For example, for k = 3 the stamps , and are successful, while the stamps (l = 1), (l = 2) and (l = 1, 2, 3) are not.
You are given queries. For each query, count the number of successful stamps consisting of cells painted in colors. Since the answers can be very large, output them modulo 10^9 + 7.
The first line contains a single integer (1 \le t \le 10^5) — the number of queries.
Each of the following lines contains two integers and (1 \le n \le 10^6, 1 \le k \le 10^9) — the number of cells of the stamp and the number of colors.
It is guaranteed that the sum of over all queries does not exceed 10^6.
For each query, print on a separate line the number of successful stamps consisting of cells painted in colors, modulo 10^9 + 7.
Example 1
Example 2
In the first example:
For n = 1 all stamps are successful.
For n = 2, k = 3 a stamp is successful if and only if its two cells have different colors: 3 \cdot 2 = 6 stamps.
For n = 3, k = 2 the successful stamps are , , and .
For n = 4, k = 2 the successful stamps are , , , , and . For example, the stamp is not successful because its first two cells are colored the same as its last two, and the stamp is not successful because it starts and ends with color .