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:
$U$
can be labeled if either $U$
is the root node or the parent node of $U$
is already labeled.$V$
only if the last labeled node was given value $V - 1$
. If no node was labeled before, $V = 1$
should be used.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:
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
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 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.
$1 \leq T \leq 100$
$1 \leq P \leq 10^6$
It is guaranteed that $P$
is a prime number in all subtasks.
$1 \leq N, K \leq 10^{6}$
$Q = 1$
$1 \leq N \leq 10^{12}$
$1 \leq K \leq 2$
$Q = 1$
$1 \leq N \leq 10^{12}$
$1 \leq K \leq 10^6$
$Q = 1$
$1 \leq N \leq 10^{12}$
$1 \leq K \leq 10^6$
$1 \leq P^Q \leq 10^6$
$Q \geq 1$
For each testcase, print $\frac{\displaystyle F(N, K)}{\displaystyle P^Z} \pmod {P^Q}$
in a single line.
Input | Output |
---|---|
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 |
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.
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.