Có 1 hàng rào gỗ có \(n\) thanh gỗ và bảng màu gồm có \(k\) màu. Chủ nhà yêu cầu chỉ sơn tối đa 2 thanh gỗ cạnh nhau cùng 1 màu. Hãy cho biết có bao nhiêu cách sơn thỏa điều kiện nhé.

Ghi chú: Vì kết quả có thể rất lớn nên hãy in kết quả sau khi mod \(10^9 + 7\)

Input

• Dòng đầu tiên là số bộ test \(t\).
• \(t\) dòng tiếp theo mô tả \(t\) bộ test. Mỗi bộ test gồm có \(n\) và \(k\) trên cùng 1 dòng và cách nhau bởi khoảng trắng.

Output

• Với mỗi bộ test, output trên 1 dòng riêng biệt kết quả tính được.

Constraints

• \(1 \le n,k \le 30\)
• \(1 \le t \le 10^3\)

Example

Sample input

2
2 4
3 2

Sample output

16
6