All Tracks Math Number Theory Problem

Mike is bored of living in his 3-dimensional house. So he wants to build a house for him in a $$K$$-dimensional space. He doesn't even know if $$K$$-dimensional space exists!. He accidentally has found that if you pass inside a Black Hole named "Aria" (This black hole is discovered by him), you enter a $$K$$-dimensional space.

Mike wants to build $$N$$ houses (hypercubes), where the side length of the $$i_{th}$$ house is $$A * i + B$$ for $$i \in [1, N]$$. There are exactly $$K$$ coordinate axes in a $$K$$-dimensional space. Each coordinate axis extends up to length $$V$$. Mike starts his journey of building houses from the origin (i.e ($$0$$, $$0$$, $$0$$, ... $$0$$)). Mike builds the houses in a peculiar way as described below.

1. This step and for all the below steps, assume that he is currently at point ($$X_1$$, $$X_2$$, .. , $$X_k$$). If he has travelled length $$V$$ along any one of the coordinate axes, stop the process. (i.e., if $$X_j = V$$ for some $$j \in [1, K]$$)
2. If he choose not to build any house, he moves $$+1$$ distance towards any one coordinate axis. (i.e. he moves to ($$X_1 + 1$$, $$X_2$$, ... $$X_k$$) or ($$X_1$$, $$X_2 + 1$$, ..., $$X_k$$) or ... ($$X_1$$, $$X_2$$, ..., $$X_k + 1$$)). Then repeat the process from step $$1$$.
3. If he choose to build the house, first he will choose an integer $$i \in [1, N]$$ which he had not chosen in any previous steps, then he will build $$i_{th}$$ house. After building the $$i_{th}$$ house he moves $$A * i + B$$ distance towards all the coordinate axes. (i.e. he moves to point ($$X_1 + A * i + B$$, $$X_2 + A * i + B$$, ...., $$X_k + A * i + B$$)). Note that he is able to build the $$i_{th}$$ house only if $$X_j + A * i + B \leq V$$ for all $$j \in [1, K]$$. Then repeat the process from step $$1$$.

Mike is eager to move to his new houses. He asks you the number of different ways he can build those $$N$$ houses. Two ways are considered different if there exists some $$i \in [1, N]$$ such that position of $$i_{th}$$ house in a first way is different from its position in a second way. As the answer can be large, print it modulo $$M$$.

Input format

The first line contains $$T$$, the number of test cases.
Each of the next $$T$$ lines contains $$6$$ space separated integers, $$V$$, $$N$$, $$K$$, $$A$$, $$B$$, $$M$$.

Output format

For each test case, print the required answer modulo $$M$$ in a single line.

Constraints

$$1 \leq T \leq 5$$
$$1 \leq V, N, K \leq 10^9$$
$$0 \leq A, B \leq 10^9$$
$$A + B \geq 1$$
$$3 \leq M \leq 10^9$$
Let $$P$$ be any prime divisor of $$M$$, then
$$3 \leq P \leq 10^5$$