# Problem C

Counting Trees

The Great Lord Pooty likes trees and orders his subordinates to have them colored black and white. The trees have $n$ vertices labeled from $0$ to $n-1$, are rooted at vertex $0$, and have a peculiar structure elaborated on below.

A tree has a fixed branching factor $k \geq 1$, meaning that every vertex labeled $v$ that is not the root ($v > 0$) will have vertex $\lfloor \frac{v-1}{k}\rfloor $ as its parent. For example, if $k = 2$, the tree is a complete binary tree.

Then, the tree would have its vertices colored either black
or white. After every vertex is colored, **all edges connecting vertices of different colors
will be removed**, resulting in a forest with many trees. We
call a coloring $c$-good,
if the final result is a forest with *exactly*
$c$ trees.

The Great Lord would like to ask you: given a tree of $n$ vertices with branching factor $k$, how many $c$-good coloring is possible? Note that two colorings are considered different if and only if there exists a vertex that is colored differently.

Since the answer can be huge, output it modulo $10^{10} + 3233 = 10\, 000\, 003\, 233$.

Of course, one tree is too simple. Since you had boldly claimed you are the smartest one in His Empire, Lord Pooty, in all his magnificent glory, demands you to answer for $C$ trees or face a gruesome end under his fist of absolute terror.

## Input

The input starts with a line containing an integer $C$, denoting the number of test cases ($1 \leq C \leq 200\, 000$).

Each test case consists of three integers $n$, $k$, and $c$, denoting the number of vertices of the tree, the branching factor, and the number of trees in the resulting forest ($1 \leq n,k,c \leq 10^{18}$).

## Output

For each test case, output a line containing the number of $c$-good colorings of the tree, modulo $10\, 000\, 003\, 233$.

Sample Input 1 | Sample Output 1 |
---|---|

5 3 2 1 7 6 4 5 7 3 4 2 4 1000000000000000000 3233 3233 |
2 40 12 2 8112035382 |