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 house is for . 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 such that position of 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.
Let P be any prime divisor of M, then
Subtask | Points |
---|---|
and | |
and | |
and | |
M is Prime | |
Original Constraints |
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.