Tổng GCD

Bạn được cho một dãy số nguyên có độ dài \(n\):

trong đó mỗi phần tử \(a_i\) (\(1 \le i \le n\)) được chọn từ tập hợp:

Rõ ràng có tất cả \(K^n\) dãy như vậy.

Nhiệm vụ của bạn: Hãy tính tổng của giá trị

trên toàn bộ \(K^n\) dãy hợp lệ.

Kết quả có thể rất lớn, do đó bạn chỉ cần in ra phần dư của kết quả chia cho \(10^9+7\).

Ghi chú: \(\gcd(x,y)\) ký hiệu ước chung lớn nhất của \(x\) và \(y\).

Input

• Dòng đầu tiên chứa số nguyên \(t\) (\(1 \le t \le 10\)), là số lượng bộ test.
• \(t\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(N\) và \(K\) (\(2 \le N \le 10^5\), \(1 \le K \le 10^5\)).

Output

• Với mỗi bộ test, in ra một số nguyên duy nhất là kết quả của bài toán, sau khi chia lấy dư cho \(10^9 + 7\).

Example

1
2 2

5