Tổng GCD

Xem PDF

Điểm: 500 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho dãy số nguyên gồm \(n\) phần tử \(a_1,a_2,...,a_n\) với \(a_i(1\le i\le n)\) thuộc tập hợp \(\left\{1,2,3,...,K\right\}\)

Như vậy, tức là có \(K^N\) dãy như vậy.

Yêu cầu: Tính tổng của tất cả \(gcd(a_1,a_2,...,a_n)\) của \(K^N\) dãy trên.

Ghi chú: \(gcd(x,y)\) tức là ước chung lớn nhất của hai số \(x,y\)

Input

  • Dòng thứ nhất chứa số \(t(1\le t\le 10)\) - Thể hiện số testcase

  • \(t\) dòng tiếp theo,ứng với mỗi dòng, gồm \(2\) số nguyên \(N,K(2\le N\le 10^5,1\le K\le 10^5)\)

Output

  • Ứng với mỗi testcase, in ra đáp án cần tìm mod \(10^9+7\)

Example

Test 1

Input
1
2 2
Output
5
Note

Giải thích: \(gcd(1,1)+gcd(1,2)+gcd(2,1)+gcd(2,2)=1+1+1+2=5\)


Bình luận


  • 3
    minhtuanitk20    10:59 p.m. 24 Tháng 1, 2022

    bài này sài binpow module với công thức quy hoạch