Bỏ qua đến nội dung

Zsum

Mã bài: myt0089 Nhóm: Training Dạng bài: Simple Math

Giới hạn thời gian
1,0 s
Giới hạn bộ nhớ
256 MB
Điểm
5một phần
Tỉ lệ AC
26,2%
Người giải
18

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

Bình luận