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
2021-05-05 06:55:23 [Lakshman]
@parth2002 Yes. 754901378 is correct answer
2021-05-04 19:20:57
Can anyone confirm if the output for input

1
100000 100000 100000

is

754901378?
2021-02-14 10:35:27
These cases were enough to get accepted:
a^0 = 1
C(0,0)=1.
2020-04-10 03:26:49
gud question
2020-01-26 10:36:24
Please don't refer to the github code , for checking your code....
Because it contain wrong answers....
ex. for test case 10 10 10
it gives...669572223
but actual answer is ...330427784

Last edit: 2020-01-26 11:48:26
2018-05-09 06:27:15
what is the output for:
1
2 2 2
2017-02-10 19:09:38 Francky
Now doable using Python3.
2017-01-24 15:14:05
can't pass test # 8 , tried all base case with 0^0;
plz.. can anybody help me ??
2016-07-10 19:27:26
for those struggling with test case 7 or 8 and getting everything correct, then most probably u won't get what needs to be done by debuging , just try to make ur code more stronger and read the comments.
2016-07-10 18:50:30
@Francky please all the tell the answer of your proposed testcases ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.