Đếm số lượng bộ số nguyên không âm ~(x, y, z)~ thỏa mãn: ~x^d + y^d + z^d \equiv m \pmod N~ ~0 \le x, y, z \le U~

Yêu cầu: Hãy tính số lượng bộ số thỏa mãn điều kiện trên, kết quả lấy phần dư khi chia cho ~10^9 + 7~. Giả thiết rằng ~0^0 = 1~.

Input

• Dòng đầu tiên ghi số nguyên dương ~T~ là số lượng bộ dữ liệu.
• Tiếp theo là ~T~ dòng, mỗi dòng ghi 4 số nguyên ~d, N, m, U~.

Output

• Với mỗi bộ dữ liệu, in ra số lượng tìm được sau khi lấy phần dư cho ~10^9 + 7~.

Sample Input 1

2 2 3 5
1 2013 3 31

Sample Output 1

4
1