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$