Ninja observed the prices of a certain stock for some days. He found an interesting pattern in the prices of the stock. Let P(i) be the price of the stock on the ‘ith’ day. He observed that
P(i) = P(i-1) + P(i-2) + P(i-1) * P(i-2)
You are given the stock prices on the first day and the second day. Your task is to determine the price of the stock on the ‘Nth’ day if the prices followed the same pattern.
Input Format :
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow.
The first line of each test case contains three space-separated integers, ‘A’, ‘B’ and ‘N’ Where ‘A’ and ‘B’ denote the prices on the first and second days respectively. ‘N’ denotes the day on which the stock price needs to be calculated.
Output Format :
For each test case, print a single integer, denoting the price of the stock on the ‘Nth’ day. Since the answer can be very large, calculate the answer modulo 10^9+7.
Output for each test case will be printed in a separate line.
You do not need to print anything. It has already been taken care of. Just implement the given function.
1 <= T <= 10
1 <= A,B, <= 10^9
3 <= N <= 5000
Time Limit: 1sec
Sample Input 1 :
1 7 3
Sample Output 1 :
Explanation For Sample Input 1 :
In the given test case, the price on day 1 is 1, and the price on day 2 is 7. We can calculate the price on day 3 using these two values. Price on day 3 will be 1 + 7 + (1*7) = 15.
Sample Input 2 :
1 3 4
Sample Output 2 :
Explanation For Sample Input 2 :
In the given test case, the price on day 1 is 1, and the price on day 2 is 3. We can calculate the price on day 3 using these two values. Price on day 3 will be 1 + 3 + (1*3) = 7. Similarly, price on day 4 will be 3 + 7 + (3*7) = 31.