You are given a pair (a,b) . After each unit of time, pair (a,b) gets changed to (ba,b+a). You are given the initial value of pair and an integer n and you have to print the value of the pair at the nth unit of time.

Input format

• First line: t denoting the number of test cases
• Next t lines: Three space-separated integers a, b, and n

Output format

• For each test case, print two integers (mod 109+7) per line denoting the value of the pair at the nth unit time.

Constraints

1t105

0ab109

1n109

SAMPLE INPUT

5 1 3 5 2 3 9 3 13 28 42 999 1881 4 97 43

SAMPLE OUTPUT

4 12 32 48 81920 131072 728771468 762921230 8388608 203423744 

Explanation

Test case 1:

At n = 1, the pair will be (1, 3).

At n = 2, the pair will be (2, 4).

At n = 3, the pair will be (2, 6).

At n = 4, the pair will be (4, 8).

At n = 5, the pair will be (4, 12).

Can you solve this in C?