Migrated from Lutece 477 A number sequence problem

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Here is a general term of a number sequence

$G(n)=(\sqrt{a}+\sqrt{b})^{2n}+(\sqrt{a}-\sqrt{b})^{2n}$

You are asked to calculate it mod $10^9+7$.

Input

The first line of the input contains a positive integer $T$($T\leq 2000$) representing the number of test cases.

Then for every case, only one line containing $3$ positive integers $a$, $b$, and $n$. ($0\leq a,b,n\leq 10^8$)

Output

For each case output one line contained the answer.

Samples

3
2 3 1
2 2 2
1 1 2

10
64
16

Resources

2011 UESTC ACM Training for Math