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.