Mike's visit to a Black Hole

5

1 votes
Combinatorics, Dynamic Programming, Medium, CRT
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 ith house is Ai+B for i[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 (X1, X2, .. , Xk). If he has travelled length V along any one of the coordinate axes, stop the process. (i.e., if Xj=V for some j[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 (X1+1, X2, ... Xk) or (X1, X2+1, ..., Xk) or ... (X1, X2, ..., Xk+1)). Then repeat the process from step 1.
  3. If he choose to build the house, first he will choose an integer i[1,N] which he had not chosen in any previous steps, then he will build ith house. After building the ith house he moves Ai+B distance towards all the coordinate axes. (i.e. he moves to point (X1+Ai+B, X2+Ai+B, ...., Xk+Ai+B)). Note that he is able to build the ith house only if Xj+Ai+BV for all j[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[1,N] such that position of ith 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

1T5
1V,N,K109
0A,B109
A+B1
3M109
Let P be any prime divisor of M, then
3P105

Subtask Points
1K3 and 1V,N10 10%
1V103 and 1N10 10%
A=0 and B=1 10%
M is Prime 20%
Original Constraints 50%
Sample Input
2
4 2 1 1 0 27
4 2 2 0 2 278421569
Sample Output
6
2
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

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.

Editor Image

?