Cho hai số nguyên ~n, k~. Hãy lập trình tính tổng ~Z_n +Z_{n-1} - 2Z_{n-2}~, với ~Z_n = S_n+P_n~ trong đó ~S_n = 1^k +2^k+\ldots +n^k~ và ~P_n =1^1 +2^2+\ldots+n^n~.

Input

Dòng đầu tiên chứa số nguyên ~T~ là số testcase thỏa ~T \le 10~.

~T~ dòng tiếp theo mỗi dòng chứa hai số nguyên ~n, k~ thỏa ~ \le n \le 200000000; 0 \le k \le 1000000~.

Output

Ứng với mỗi testcase in ra số cần tính, do dữ liệu lớn nên cần modulo cho ~10^9+7~.

Examples

Sample Input

2
3 4
123 45

Sample Output

148
318867558