Your younger brother's teacher gave him this simple problem.

Given b and c. Evaluate the result of this expression:

• Result₁ = b^c

Your brother definitely was able to solve this easy problem. So his teacher decided to give him a bit harder problem.

Given a, b and c. Evaluate the result of this expression:

• Result₁ = b^c
• Result₂ = a^Result₁

However, your brother was also able to solve it. It was not that hard. His teacher was excited though and gave him this Bonus Programming Assignment.

Write a program that is given a, b and c; calculates the value of Result₂. Since the output may be exponentially very large, checking the correctness of solutions will be a bit of a problem. So, instead of printing the whole value of Result₂, just print the remainder of dividing Result₂ by 1,000,000,007 (10⁹ + 7).

Can you help him solve that task?

Input

The input consists of several test cases. Each case is on a single line. In each case, given three space separated integers a, b and c (0 <= a, b, c <= 2³¹ - 1). The input is terminated by a = b = c = -1

Output

For each case, print exactly one line containing the value of Result₂ modulus 10⁹ + 7

Example

Input:
2 2 2
3 4 5
-1 -1 -1

Output:
16
763327764

Note

You can assume that 0⁰ = 1.