All Tracks Math Number Theory Problem

Mike's visit to a Black Hole

CRT, Combinatorics, Dynamic Programming, Medium


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.


$$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\%$$
4 2 1 1 0 27
4 2 2 0 2 278421569

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++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in

National Institute of Technology, Surathkal

Challenge Name

Inscription '16

View All Notifications