POWPOW - Power with Combinatorics
Your task is to find aexpb,
a: Provided in input, 0 ≤ a ≤ 105
b: Provided in Input, 0 ≤ b ≤ 105
exp = (nC0)2 + (nC1)2 + (nC2)2 + ... + (nCn)2,
n: Provided in the input, 0 ≤ n ≤ 105
As the answer can be too large, you need to output modulo 109+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 121 is 1, so output is 1.
hide comments
|
Rajesh Kumar:
2013-09-04 04:42:20
huuhhhh... Finally DOne...
|
|
Shaily Mittal:
2013-09-04 04:42:20
Can you provide some more test cases for big values og a,b and n?
|
|
Himanshu Srivastava:
2013-09-04 04:42:20
is there any special case....why i get wrong answer at running judge 8??
|
|
Mitch Schwartz:
2013-09-04 04:42:20
@Devendra: Thanks for your response. But for me the original version of the problem is more interesting. I don't know how you feel about it -- whether you would be willing to change it back to a^b^exp (but with corrected test data), or maybe have a^b^exp version added as a separate problem. If you can't solve a^b^exp version at this time, maybe I could add it (I haven't solved it yet, but I know a way), although I prefer to be able to compete on it. Also I think it's worth reiterating Francky's earlier comment about whether the time limit is appropriate for slower languages like Python.
|
|
devu:
2013-09-04 04:42:20
@Francky,Mitch Schwartz:Thanks for pointing out the error,actually i thought for a^(exp^b) bt what lead me to calculate a^(b^exp) with same logic has no explanation,I apologize to all the users who put up their valuable time to solve that one,I hope that this one is a correct one. |
| 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 |
RSS