Chotu being brother of Mojo Jojo wants to take revenge from Powerpuff Girls for insulting Mojo Jojo.
Chotu hates the Powerpuff girls - hates them to the core. He hates the fact that every single one of those girls have a huge number denoting their power constant. Here are their respective powers: A1d , A2d and A3d .
Chotu wants to find out the exact power units he would need to defeat the powerpuff girls. To find that out, he would need the number of solutions of equation :
A1d + A2d + A3d ≡ M (modulo N)
The above equation should satisfy the following constraint : 0 <= A1, A2, A3 <= Upper Limit.
A1, A2, A3 should also be integers.
Input
First line contains an integer T denoting number of test cases.
Next T lines contain four integers Upper Limit, d, M and N respectively.
Output
For each test case print total number of solutions for above equation. Since answer may be too large print answer modulo 109+7
Constraints
1 <= T <= 10
1 <= Upper Limit <= 1018
0 <= d <= 1018
1 <= N <= 100
0 <= M < N
Note : Consider 00 equal to 1 for this question.
Note : A ≡ B (modulo P) means A modulo P = B modulo P
In Test Case 1 :
A1, A2 and A3 can take value 0, 1 or 2.
Therefore following are possible situations :
02 + 02 + 02 = 0 + 0 + 0 = 0 ≡ 0 (modulo 5)
02 + 02 + 12 = 0 + 0 + 1 = 1 ≡ 1 (modulo 5)
02 + 02 + 22 = 0 + 0 + 4 = 4 ≡ 4 (modulo 5)
02 + 12 + 02 = 0 + 1 + 0 = 1 ≡ 1 (modulo 5)
02 + 12 + 12 = 0 + 1 + 1 = 2 ≡ 2 (modulo 5)
02 + 12 + 22 = 0 + 1 + 4 = 5 ≡ 0 (modulo 5)
02 + 22 + 02 = 0 + 4 + 0 = 4 ≡ 4 (modulo 5)
02 + 22 + 12 = 0 + 4 + 1 = 5 ≡ 0 (modulo 5)
02 + 22 + 22 = 0 + 4 + 4 = 8 ≡ 3 (modulo 5)
12 + 02 + 02 = 1 + 0 + 0 = 1 ≡ 1 (modulo 5)
12 + 02 + 12 = 1 + 0 + 1 = 2 ≡ 2 (modulo 5)
12 + 02 + 22 = 1 + 0 + 4 = 5 ≡ 0 (modulo 5)
12 + 12 + 02 = 1 + 1 + 0 = 2 ≡ 2 (modulo 5)
12 + 12 + 12 = 1 + 1 + 1 = 3 ≡ 3 (modulo 5)
12 + 12 + 22 = 1 + 1 + 4 = 6 ≡ 1 (modulo 5)
12 + 22 + 02 = 1 + 4 + 0 = 5 ≡ 0 (modulo 5)
12 + 22 + 12 = 1 + 4 + 1 = 6 ≡ 1 (modulo 5)
12 + 22 + 22 = 1 + 4 + 4 = 9 ≡ 4 (modulo 5)
22 + 02 + 02 = 4 + 0 + 0 = 4 ≡ 4 (modulo 5)
22 + 02 + 12 = 4 + 0 + 1 = 5 ≡ 0 (modulo 5)
22 + 02 + 22 = 4 + 0 + 4 = 8 ≡ 3 (modulo 5)
22 + 12 + 02 = 4 + 1 + 0 = 5 ≡ 0 (modulo 5)
22 + 12 + 12 = 4 + 1 + 1 = 6 ≡ 1 (modulo 5)
22 + 12 + 22 = 4 + 1 + 4 = 9 ≡ 4 (modulo 5)
22 + 22 + 02 = 4 + 4 + 0 = 8 ≡ 3 (modulo 5)
22 + 22 + 12 = 4 + 4 + 1 = 9 ≡ 4 (modulo 5)
22 + 22 + 22 = 4 + 4 + 4 = 12 ≡ 2 (modulo 5)
Hence there are 4 equations which are equivalent to 3 with respect to modulus 5.
