A shop wants to commercialize a new kind of jewellery: toric necklaces! Given an infinite supply of k different beads, a toric necklace is built by picking n · m beads and placing them on an n× m grid. Then we join every pair of beads that are vertically adjacent with blue thread, and every pair of beads that are horizontally adjacent with red thread. Finally, we use blue thread to join the j-th bead of the first row with the j-th bead of the last row, and red thread to join the i-th bead of the first column with the i-th bead of the last column.

Here, we consider two toric necklaces equivalent if one can be obtained from the other by horizontal and/or vertical rotations. In other words, two necklaces defined by the matrices A[0… n−1,0… m−1] and B[0… n−1,0… m−1] are equivalent if there exist x and y such that A[i,j] = B[(i+x) modn, (j+y) modm] for every i and j.

Given n, m and k, can you compute the number of different toric necklaces?

Input

Input consists of several different cases, each one with n, m and k,
all between 1 and 10^{6}.

Output

For every case,
print the number of n× m toric necklaces
that can be built with beads of k different kinds,
modulo 10^{9} + 7.

Public test cases

**Input**

1 2 2 1 2 3 2 2 2 2 3 3 3 5 1 4 6 2 1 1 500 10 20 30 720680 33199 792347 1000000 1000000 1000000

**Output**

3 6 7 130 1 699600 500 798528669 229776682 320081768

Information

- Author
- Lander Ramos
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Tretzè Concurs de Programació de la UPC - Semifinal
- Date
- 2015-07-01