Số lượng nghiệm

Xem PDF

Đ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

Không có bình luận nào.