H. Möbius Band Coloring
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You have a transparent band of length N units and width M units. It's split into $$$N \times M$$$ unit squares.

You take two sides of the band (the ones with length M units), rotate one of them by 180 degrees, and connect them, getting a Möbius band of length N and width M. Then you paint each square on the band in one of $$$K$$$ colors.

Two painted Möbius bands of the same size are considered to have the same coloring if you can move one of them in such a way that it becomes indistinguishable from the other one. Otherwise, they have different colorings.

Find the number of colorings of the given Möbius band in K colors, modulo $$$10^9+7$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1\le t \le 100$$$). The description of the test cases follows.

Each test case contains 3 integers $$$N,M,K$$$ on a single line. $$$1 \le N \le 10^9$$$. $$$1 \le M,K \le 10^{18}$$$.

Output

For every test case, output a single integer on a separate line — the number of colorings, modulo $$$10^9+7$$$.

Example
Input
6
2 2 2
3 5 2
1 3 2
3 1 2
40 6 3
100 200 1
Output
6
3100
6
4
907960343
1
Note

The picture below shows 4 instances of the same coloring for $$$N=40, M=6, K=2$$$.