Migrated from Lutece 472 Easy math

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

In this problem,you will be give three positive integers,and you are to calculate $a^{b^c}\ mod\ 1000000007$.

Input

Each line of input will contain three positive integers:$a,b,c\leq 1000000000$.

Output

For each case, print a number index the answer.

Samples

2 2 2

16

2 3 2

512

Resources

recommend by liverliu