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$.

5
3 2 1
7 6 4
5 7 3
4 2 4
1000000000000000000 3233 3233

2
40
12
2
8112035382