You're given three numbers: , , and , and all you have to do is to find the number where
As the number can be very large, output it modulo .
Consider the following link: http://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form
Input Format
First line contains a single integer - the number of tests. lines follow, each containing three integers: , and .
Constraints
Output Format
For each test case output a single integer .
Sample Input
8
2 3 1
9 1 7
9 8 3
2 4 9
1 7 2
1 8 1
4 3 1
3 7 5
Sample Output
3
85
25
178
8
8
3
44
Explanation
First test case is obvious.
Let's look through the second one: