POWPOW - Power with Combinatorics

Your task is to find a^(exp^(b)),

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 the input, 10^5 => n >= 0

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

nCr denotes n choose r.

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^(2^1) is 1, so output is 1.

Click here to see my set of problems at Spoj.


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

hide comments
2023-03-20 17:39:41
Tips:
- would start with little fermat and derive exp^b in terms of mod p-1
- afterwards, use vandermon to derive simplification of exp
- then, use chinese remainder thereom to find C(2n, n)
- rest is straightforward
2021-07-09 19:41:28
What is there in test case 8 :(
Got so many WAs without even a hint.
Please help...
------edit------
Finally removed from todo list after 10 months...
No words to describe the beauty of the problem...

Last edit: 2022-05-07 11:24:52
2019-06-15 09:08:12
Pre requisites:
1. Fermat's little theorem
2. Lucas theorem
3. Chinese remainder theorem
4. Modular exponentiation
5. Modular multiplicative inverse
6.Extended Euclidean Theorem

For those getting WA on test case 8:
Try to check your computation for exp

For those getting TLE on test case 8:
Try to do some pre computation

Excellent problem to get strengthen all your mathematical concepts in competitive coding .
AC after 8 attempts after getting WA and TLE on test case 8

Last edit: 2019-06-15 09:10:57
2018-05-09 06:01:44
Anyone please comment the result for:
1
2 2 2
2017-01-10 03:39:44
Wow What a question
My 50th :)

Last edit: 2017-01-21 14:41:57
2015-07-20 15:53:13 Tanzir Islam
I got ac in this problem. However, there's something weird about this problem.
In my solution, I wrote the function to calculate power like this,
long long power(long long a, long long b, long long p)
{
if(a == 0)
return 0;
......
}
I got wa. Then I removed this if condition, I got ac. 0^b should be 0 for any value of b, shouldn't it ?
2015-01-25 14:59:55 Sayak Haldar
@psetter, is 0^0=1? like in powpow2 and tutorial version of it?
edit 1: anyone who solves this problem, please help me by giving the answer..

Last edit: 2015-01-25 15:39:21
2014-12-10 16:44:28 i need you
getting wrong answer in 8th judge...please suggest
edit-done!

Last edit: 2015-02-02 11:29:09
2014-11-30 17:34:32 Mayank Ladia
testcase 8.. WA now :(

Last edit: 2015-07-13 23:02:16
2014-07-28 15:37:21 tapan sahni
getting nzec in java ...what to do
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.