SPOJ.com - Problem POWPOW

POWPOW - Power with Combinatorics

no tags

Your task is to find a^{exp^b^,}

a: Provided in input, 0 ≤ a ≤ 10⁵

b: Provided in Input, 0 ≤ b ≤ 10⁵

exp = (nC0)² + (nC1)² + (nC2)² + ... + (nCn)²,

n: Provided in the input, 0 ≤ n ≤ 10⁵

As the answer can be too large, you need to output modulo 10⁹+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¹ is 1, so output is 1.

Click here to see my set of problems at Spoj.

Submit solution!

hide comments

< Previous 1 2 3 Next >

	origin_beta: 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
	sankalp_7: 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
	abhinav_jain02: 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
	kmkhan_014: 2018-05-09 06:01:44 Anyone please comment the result for: 1 2 2 2
	yash_code_guy: 2017-01-10 03:39:44 Wow What a question My 50th :) Last edit: 2017-01-21 14:41:57
	Tanzir Islam: 2015-07-20 15:53:13 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 ?
	Sayak Haldar: 2015-01-25 14:59:55 @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
	i need you: 2014-12-10 16:44:28 getting wrong answer in 8th judge...please suggest edit-done! Last edit: 2015-02-02 11:29:09
	Mayank Ladia: 2014-11-30 17:34:32 testcase 8.. WA now :( Last edit: 2015-07-13 23:02:16
	tapan sahni: 2014-07-28 15:37:21 getting nzec in java ...what to do

Submit solution!

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