SPOJ.com - Problem POWPOW2

POWPOW2 - Power with Combinatorics(HARD)

no tags

Your task is to calculate a^(b^(exp)).

a: provided in input, 10^5 >= a >= 0
b: provided in input, 10^5 >= b >= 0
exp = (nC0)^2 + (nC1)^2 + (nC2)^2 + ... +(nCn)^2
n: provided in input, 10^5 >= n >= 0

Note: The Output for 0^0 should be 1.

nCr denotes n choose r.

As the answer can be too large, you need to output modulo 10^9+7.

Input

The first line of each input file contains number of test cases t (t<=1000).

Then follow a new line.

Then follow t lines, each containing 3 integers, (i.e. a b n in order) each of them separated by a space.

Output

Output contains t lines, ith line contains the answer of the ith test case.

Example

Input:
1

1 1 1

Output:
1

Explanation

In First test case, the Value of exp is 2, value of 1^(1^2) is 1, so output is 1.

Note: First try out the tutorial version where limits are low. POWRTU

Click here to see my set of problems at SPOJ.

Submit solution!

hide comments

< Previous 1 2 3 4 Next >

	Francky: 2013-09-04 04:43:08 I did my best and it seems that a Python solution is not possible or ultra hard. I think it would be fine to allow python solution with a little more time, it would still reject bad complexity / fast language solutions. IMHO.
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2013-09-04 04:43:08 Nice problem! Need a lot of thinks and optimizations to solve it. But my program getting WA... Can you tell me which case that cause my program wrong (ID: 7325908)? Input: 1 79981 79981 79981 Output: 79981 is this correct? Re:It is Correct. Edit: Then why my program wrong? I don't know which case that cause my program wrong. Can you tell me one case that cause my program wrong? Re:I am Srry, i cant tell u any case which might lead to wa,bt as far as tricky cases ,check for 0^0 condition ,if it gives wa again,then rethink ur logic Edit: Thanks for your reply. Now I'm finding for a case that cause my program wrong. My pow() function already correct for 0^0=1 Edit: Thanks for your hint :) Although I still getting WA (After handling tricky test cases)... Last edit: 2012-07-16 20:10:25
	Mitch Schwartz: 2013-09-04 04:43:08 Interesting, while debugging I found an error (although easily corrected) in a published paper. I can't be more specific without spoiling, but some others may come across it too so be careful. Re:Yeah,right said ,It took me a lot of time to think a correct mathematical solution before hosting the problem. Last edit: 2012-07-15 17:21:44
	devu: 2013-09-04 04:43:08 Solutions are rejudged,Damian Straszak and Anton Lunyov are accepted, I uploaded the previous input output file,sorry for the inconvinience caused. I hope in my next problem ,i will not make this error for sure.

Submit solution!

Added by:	devu
Date:	2012-07-14
Time limit:	0.100s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	Utkarsh Lath