SOLVE
LATER
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.
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$$.
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$$.
For each test case, print the required answer modulo $$M$$ in a single line.
$$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$$
Subtask | Points |
---|---|
$$1 \leq K \leq 3$$ and $$1 \leq V, N \leq 10$$ | $$10\%$$ |
$$1 \leq V \leq 10^3$$ and $$1 \leq N \leq 10$$ | $$10\%$$ |
$$A = 0$$ and $$B = 1$$ | $$10\%$$ |
$$M$$ is Prime | $$20\%$$ |
Original Constraints | $$50\%$$ |
For the first test case, consider orange as house $$2$$ and green as house $$1$$. hypercube in one dimension is a straight line :). So there are $$6$$ possibilities to build $$2$$ houses.
For the second case, consider green as house $$1$$ and red as house $$2$$. So there are two different configurations of $$2$$ houses possible.