POWERUP - Power the Power Up

no tags 

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

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

  • Result1 = bc

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:

  • Result1 = bc
  • Result2 = aResult1

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 Result2. 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 Result2, just print the remainder of dividing Result2 by 1,000,000,007 (109 + 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 <= 231 - 1). The input is terminated by a = b = c = -1

Output

For each case, print exactly one line containing the value of Result2 modulus 109 + 7

Example

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

Output:
16
763327764

Note

You can assume that 00 = 1.


hide comments
lighted: 2020-10-09 19:33:35

Nice tricky cases!

Amit Ajaat: 2015-07-07 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: 2015-06-25 20:49:25

can you please give testcase for which my code fails?? ID==14536832

Yosvany (BeCrazy): 2015-03-27 15:25:33

Please provide test case for which my code fails? id is 13965026

Nikhil Sheoran: 2015-03-06 09:40:38

Awesome tricky cases..Loved solving this problem..

Last edit: 2015-03-06 09:41:00
Subhendu Sethi: 2015-01-21 20:21:40

Where am I lagging behind. Really have thought of every corner case!! Hers is my id=>13486933. Moderator help please.

EDIT: Never Mind AC after may WA's!

Last edit: 2015-01-22 00:32:52
Martijn Muijsers: 2015-01-19 15:56:02

Thanks for reply! :) I'll keep searching.
(Test cases removed to let you guys have fun too)

--Francky--> We agree that your sample are correct. Test cases are OK ; there's another kind of tricky cases. Good luck.

Last edit: 2015-01-19 16:14:08
Sai Charan Movva: 2015-01-07 10:54:36

Please help me where i'm getting wrong
id-(13365486)...with some tricky cases..
Thanx

Abhishek: 2014-12-27 14:08:03

after 14 WA's and a single silly mistake , finally AC , ah that feeling , a real nice problem


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