Nth Element of Modified Fibonacci Series

Given two integers X and Y as the first two elements of a series, and another integer N, find the Nth number of the series utilizing the Fibonacci rule: f(x) = f(x - 1) + f(x - 2).

Note: Return the answer modulo 10^9 + 7 as it may be very large.

Note:

The series is 1-based indexed.

Input:

The first line contains an integer T representing the number of test cases. Each test case consists of a single line with three space-separated integers X, Y, and N. X and Y are the first and second elements of the series, while N is the position of the number to find.

Output:

For each test case, output a single integer representing the Nth number of the series. Each output should be on a new line.

Example:

Input:

T = 2
X = 2, Y = 3, N = 3
X = 1, Y = 1, N = 5

Output:

5
3

Constraints:

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 10^18
• -10^6 ≤ X, Y ≤ 10^6
• Time limit: 1 sec.

Note:

You are not required to print anything; it has already been taken care of. Just implement the given function.