Cho hai số nguyên dương \(n\) và \(g\). Nhiệm vụ của bạn là đếm số lượng các tập con khác rỗng của tập hợp \(\{1, 2, \ldots, n\}\) có ước chung lớn nhất (UCLN) đúng bằng \(g\).
Input
- Dòng duy nhất chứa hai số nguyên \(n\) và \(g\) (\(1 \le g \le n \le 10^6\)).
Output
- In ra một số nguyên duy nhất là đáp án của bài toán, sau khi chia lấy dư cho \(10^9 + 7\).
Example
Test 1
Input
6 2Output
5
Bình luận
Đăng nhập để bình luận
Chưa có bình luận nào.