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