NyanCoder have a new hobby, that hobby is playing with string and He love sorted string. NyanCoder want to make two strings a and b, both string have equal length N. At that both string, NyanCoder want to swap some element (or none) on string a with element on string b that located at same position. More specifically, NyanCoder may choose integer i, and then swap a[i] with b[i].

NyanCoder want when he finished playing, both new string have non-decreasing element (e.g. "aabbb", "cccdee" but not "bbaa" or "ebd"). Help NyanCoder to count number of possible initial string a and b with length N that meet the condition that NyanCoder want.

Input

First line there is an integer T denoting number of test cases, then T test cases follow.
For each test case, there is two integers N and M, separated by a space where N denoting length of both string, and alphabet that can be used on that both string is M first letters (lower case) on latin alphabet ('a','b','c', and so on). For example, if M=3, all character on both string is formed with only first 3 lower case letters ('a','b', and 'c').

Output

For each test case, output an integer which is the number of possible initial string a and b with length N and meet all condition that have described before. Since that answer can be too large, take modulo 10⁹+7

Example

Input:

1

2 2

Output:

11

Explanation

When N=2 and M=2, all pair of initial sring that meet the condition is:

1. "aa", "aa"
2. "aa", "ab"
3. "aa", "bb"
4. "ab", "aa"
5. "ab", "ab"
6. "ab", "bb"
7. "bb", "aa"
8. "bb", "ab"
9. "bb", "bb"
10. "ba", "ab"
11. "ab", "ba"

Subtask

• Subtask 1 (10 points): 1<=N<=5, 1<=M<=26
• Subtask 2 (20 points): 1<=N<=10, 1<=M<=26
• Subtask 3 (30 points): 1<=N<=40, 1<=M<=26
• Subtask 4 (40 points): 1<=N<=1000, 1<=M<=26

To get AC on this problem you need to solve at least one test data (min possible points on rank table for this problem is 10).

Other Info

This is a copy of TOKI problem, with some small changes to become suitable with SPOJ server and judge:

• Language, because SPOJ is International Online Judge, so I must translate the problem statement and other to English before publishing it.
• I/O format, because SPOJ server is busy (too many submission per minute), to make it stable then I should make number of input data as small as possible, so my solution is to put multiple test case in one file.
• Test Case, because I don't know official test case used on this problem, I build my own test case. All possible case that meet the constraints will appear once on each test data.

Problem setter who created this problem is Risan Petrus. I only copy his problem that used on TOKI open contest june 2013 to SPOJ because for me this problem is very interesting. I like it, and I want every user on SPOJ can enjoy his problem too.

See also: Another problem added by Tjandra Satria Gunawan