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: A₁^d , A₂^d and A₃^d .

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 :
A₁^d + A₂^d + A₃^d ≡ M (modulo N)

The above equation should satisfy the following constraint : 0 <= A₁, A₂, A₃ <= Upper Limit.
A₁, A₂, A₃ 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 10⁹+7

Constraints
1 <= T <= 10
1 <= Upper Limit <= 10¹⁸
0 <= d <= 10¹⁸
1 <= N <= 100
0 <= M < N

Note : Consider 0⁰ equal to 1 for this question.
Note : A ≡ B (modulo P) means A modulo P = B modulo P