Mike's visit to a Black Hole
Tag(s):

## CRT, Combinatorics, Dynamic Programming, Medium

Problem
Editorial
Analytics

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$

$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\%$
SAMPLE INPUT
2
4 2 1 1 0 27
4 2 2 0 2 278421569
SAMPLE OUTPUT
6
2
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.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala 2.11.8, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

Inscription '16

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Basic Math
• Math > Linear Algebra
• Algorithms > Graphs