Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

ACT 1: Ash Counting Trees

By Zeronfinity · Limits 3s, 512 MB

Ash Ketchum has a weird rooted tree (read Notes sections if you don’t know about tree data structure). The tree has an infinite number of nodes (vertices). Each node has exactly $K$ child nodes. Ash named such trees $K$-child trees. That means, if $K = 2$, it is called a 2-child tree and the tree is an infinite binary tree. Similarly, a 3-child tree is an infinite ternary tree and so on. Initially, all the nodes in the tree are empty.

Ash wants to label exactly $N$ nodes of such a tree with some positive integers, abiding by the following rules:
1. A tree node $U$ can be labeled if either $U$ is the root node or the parent node of $U$ is already labeled.
2. A node can be labeled with the value $V$ only if the last labeled node was given value $V - 1$. If no node was labeled before, $V = 1$ should be used.
3. A node can not be labeled more than once.

Being a mathematical genius (thanks to his Abra Kadabra Alakazam), Ash designed a function $F(N, K)$ such that:
$F(N, K)$ = the number of different $K$-child trees Ash can obtain after labeling $N$ nodes following the rules stated above.

For example, $F(3, 2) = 6$ and the six trees Ash can obtain are shown in the following image:

6_tree_example_image


But Ash likes to unnecessarily complicate things. He chose a prime number $P$ and another integer $Q$. His target is to find $F(N, K) \pmod{P^Q}$. But since it often becomes $0$, he does the following first.

He divides $F(N, K)$ by $P^Z$ such that $Z$ is maximum and $F(N, K)$ is divisible by $P^Z$. And then he finally finds

$\frac{\displaystyle F(N, K)}{\displaystyle P^Z} \pmod {P^Q}$

Your task is to help Ash find that.

In other words, given $N$, $K$, $P$ and $Q$, you have to find $\frac{\displaystyle F(N, K)}{\displaystyle P^Z} \pmod {P^Q}$

Input

Input will start with an integer $T$ in a single line, denoting the number of test cases. The following $T$ lines will represent the test cases.

In each test case, four space-separated integers $N$, $K$, $P$ and $Q$ will be given in a single line.

Constraints

$1 \leq T \leq 100$
$1 \leq P \leq 10^6$
It is guaranteed that $P$ is a prime number in all subtasks.

Subtask 1 (5 points)

$1 \leq N, K \leq 10^{6}$
$Q = 1$

Subtask 2 (15 points)

$1 \leq N \leq 10^{12}$
$1 \leq K \leq 2$
$Q = 1$

Subtask 3 (35 points)

$1 \leq N \leq 10^{12}$
$1 \leq K \leq 10^6$
$Q = 1$

Subtask 4 (45 points)

$1 \leq N \leq 10^{12}$
$1 \leq K \leq 10^6$
$1 \leq P^Q \leq 10^6$
$Q \geq 1$

Output

For each testcase, print $\frac{\displaystyle F(N, K)}{\displaystyle P^Z} \pmod {P^Q}$ in a single line.

Sample

InputOutput
7
2 2 5 1
3 2 7 1
3 2 5 1
3 2 2 1
3 2 3 1
3 3 17 1
15 5 7 1
2
6
1
1
2
15
3

Sample Explanation

First test case:

$F(2, 2) = 2$, so $Z = 0$ is the largest $Z$ such that $5^Z$ divides $F(2, 2)$.

Thus, $\displaystyle \frac{F(2, 2)}{5^0} = 2$ and answer is 2.

Second test case:

$F(3, 2) = 6$, so $Z = 0$ is the largest $Z$ such that $7^Z$ divides $F(3, 2)$.

Thus, $\displaystyle \frac{F(3, 2)}{7^0} = 6$ and answer is 6.

Third test case:

$F(3, 2) = 6$, so $Z = 0$ is the largest $Z$ such that $5^Z$ divides $F(3, 2)$.

Thus, $\displaystyle \frac{F(3, 2)}{5^0} = 6$. Here, $P^Q = 5^1 = 5$.

$\displaystyle \frac{F(3, 2)}{5^0} \equiv 1 \pmod {5^1}$, so answer is 1.

Fourth test case:

$F(3, 2) = 6$, so $Z = 1$ is the largest $Z$ such that $2^Z$ divides $F(3, 2)$.

Thus, $\displaystyle \frac{F(3, 2)}{2^1} = 3$. Here, $P^Q = 2^1 = 2$.

$\displaystyle \frac{F(3, 2)}{2^1} \equiv 1 \pmod {2^1}$, so answer is 1.

Notes

In computer science, a tree is a widely used abstract data type. A tree data structure can be defined recursively as a collection of nodes (starting at a root node), where each node is a data structure consisting of a value, together with a list of references to nodes (the “children”), with the constraints that no reference is duplicated, and none points to the root.

Discussion

Statistics


50% Solution Ratio

NirjhorEarliest, 1M ago

NirjhorFastest, 1.7s

NirjhorLightest, 131 kB

NirjhorShortest, 1522B

Submit

Login to submit

Editorial

Suppose you haven’t labeled any nodes yet. So to label the first node, how many options do you have?...