Điểm:
100 (p)
Thời gian:
2.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Đếm số lượng nghiệm
Vào thẳng vấn đề, ta cần tìm số lượng nghiệm của bất phương trình \(x^d + y^d + z^d \equiv m \ (\mod n), \ 0 \le x, y, z \le u\).
Input
- Dòng đầu tiên là 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 là bốn số nguyên \(u, d, m, n\) \((0 \le u, d \le 10^9, 0 \le m < n \le 100)\)
Output
- \(T\) dòng là đáp án cho các test, lấy dư cho \(10^9 + 7\).
Examples
Test
Input
2
100 2020 2 9
7 4 3 50
Output
152694
26
Bình luận