POWERUP  Power the Power Up
Your younger brother's teacher gave him this simple problem.
Given b and c. Evaluate the result of this expression:
Result_{1} = 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_{1} = b^{c}
^{}Result_{2} = a^{Result1}
However, your brother was also able to solve it. It was not that harder. 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_{2}. Since the output may be exponentially very large, checking the correctness of solutions will be a bit subtle problem. So, instead of printing the whole value of Result_{2}, just print the reaminder of dividing Result_{2} by 1,000,000,007 (10^{9} + 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^{31}  1). The input is terminated by a = b = c =  1
Output
For each case, print exactly one line containing the value of Result_{2} modulus 10^{9} + 7
Input
2 2 2
3 4 5
1 1 1
Output
16
763327764
Note
You can assume that 0^{0} = 1.
hide comments
Amit Ajaat:
20150707 20:31:54
please check my code 14621216 , please , i have already got more than 20 wrong submission. its enough now.........I M DAMN SURE, I M RIGHT, WHY WRONG ANSWER.... 

rajan pipaliya:
20150625 20:49:25
can you please give testcase for which my code fails?? ID==14536832 

Yosvany (BeCrazy):
20150327 15:25:33
Please provide test case for which my code fails? id is 13965026 

Nikhil Sheoran:
20150306 09:40:38
Awesome tricky cases..Loved solving this problem.. Last edit: 20150306 09:41:00 

Subhendu Sethi:
20150121 20:21:40
Where am I lagging behind. Really have thought of every corner case!! Hers is my id=>13486933. Moderator help please.


Martijn Muijsers:
20150119 15:56:02
Thanks for reply! :) I'll keep searching.


Sai Charan Movva:
20150107 10:54:36
Please help me where i'm getting wrong


Abhishek:
20141227 14:08:03
after 14 WA's and a single silly mistake , finally AC , ah that feeling , a real nice problem 

Abhishek:
20141227 13:25:31
Please provide test case for which my code fails ,13280275

Added by:  Ahmed Salem [mrtempo] 
Date:  20141106 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Palestinian Collegiate Programming Contest 2013 