POWPOW2 - Power with Combinatorics(HARD)

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.


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

hide comments
2016-07-10 18:04:16
in this problem do we need to take c(0,0) as 1 or 0 ?
it needs to be taken as 1

Last edit: 2016-07-10 19:28:03
2016-03-22 19:32:43
i think your test cases with n=0 have wrong results
2016-03-22 17:19:49
i cant understand why i m getting WA...
everything seems to work correctly....
2015-06-28 13:48:49 JY
@Francky Is the output for the test case you mention
1
1
1 ?
2014-07-16 22:44:17 Lucas Melo
My code is running really fast at my computer, about 0.040 sec. I don't understand why I can't pass the time limit.
2013-12-24 00:25:59 Shaka Shadows
Hardest math problem ever faced in my life. Thanks @Devendra Agarwal.

Re: Thanks for the Appreciation and Welcome :D

Last edit: 2013-12-24 20:12:54
2013-10-24 19:58:19 Joshi Cordova Monroy
For
1
2 2 0
The answer should be 4, but an AC submission prints a different answer.

Re: Thanks for letting me know.I think it is too late to add the test case and i would not be allowed to rejudge all submissions also.

Last edit: 2013-10-25 15:21:15
2013-09-04 04:43:08 Miguel Oliveira
Spent several days working on this problem and finally got it. This is the hardest problem I ever solved. I had to learn a lot of stuff to do it. Thank you

Re: Thanks for your Appreciation :) .

Last edit: 2013-08-20 06:09:07
2013-09-04 04:43:08 Blasters
@Sameer I think I am too late to ans that but anyways the ans is 688147711
2013-09-04 04:43:08 Blasters
Really very awesome problem. The best that I had ever faced with few tricky test cases. I wont spoil the problem by telling those but hint: remember the restriction on any theorem that you use in this problem .

Last edit: 2013-06-09 05:44:36
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.