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:

- A tree node
`$U$`

can be labeled if either`$U$`

is the root node or the parent node of`$U$`

is already labeled. - 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. - 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:

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.

Toph uses cookies. By continuing you agree to our Cookie Policy.