Nth Element Of Modified Fibonacci Series

Given two integers X and Y as the first two numbers of a series, and an integer N, determine the Nth element of the series following the Fibonacci rule: f(x) = f(x - 1) + f(x - 2).

The result may be very large, so return the answer modulo 10^9 + 7.

Example:

Input:

X = 1, Y = 1, N = 5

Output:

5

Explanation:

The series starts as 1, 1, 2, 3, 5...

Constraints:

• 1 <= T <= 100
• 1 <= N <= 10^{18}
• -10^{6} <= X, Y <= 10^{6}
• Time limit: 1 sec.

Input:

The first line contains an integer T denoting the number of test cases. For each test case, there is a line with three space-separated integers ‘X’, ‘Y’, and ‘N’ where ‘X’ and ‘Y’ are the initial numbers of the series, and ‘N’ is the position in the series.

Output:

For each test case, print the Nth number of the series, each in a new line.

Note:

The series is 1-based indexed, and you don't need to print anything manually; you need to implement the function to obtain the answer.