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 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 Result2. 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 Result2, just print the reaminder 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

Sample test(s)
Input
2 2 2
3 4 5
-1 -1 -1
Output
16
763327764

Note

You can assume that 00 = 1.


hide comments
Abhishek: 2014-12-27 13:25:31

Please provide test case for which my code fails ,13280275

knb_dtu: 2014-12-16 12:04:30

Can u please give testcase for which my code fails?(id=>13180863)

Pawankumar P: 2014-12-13 08:50:09

While scanning - int => ac long long => wa. No idea why!

Jignesh: 2014-12-01 14:00:22

nice problem, nice tricky cases

ivar.raknahs: 2014-11-24 04:35:43

can't find the tricky cases ,need help?

Sankaranarayanan G: 2014-11-19 17:47:53

I don't know where I am going wrong. Can you suggest anything?

bourne: 2014-11-18 08:24:06

According to me, the following boundary test cases and their answers -

input -
<Removed>
output -
<Removed>

Am I doing anything silly with these test cases?


--ans(Francky)--> I think these cases are correct ones, and are not spoiling the problem. Please don't post tricky cases, unless killing the problem.

@ FRancky - Thanks ! and Removed the cases. Would keep that in mind.

Last edit: 2014-11-18 08:53:17
CHANDAN KUMAR: 2014-11-15 23:03:16

Can anyone please tell me what is the tricky cases

RE: Then they wouldn't be tricky.

Last edit: 2014-11-15 23:33:57
ivar.raknahs: 2014-11-09 10:45:47

@Ahmed Salem [mrtempo]=>id(12852095)
can u please tell me if my logic is correct.?
and if my logic is correct then where am i failing?
thanks for your help


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