0

Nth Element Of Modified Fibonacci Series

Difficulty: EASY
Avg. time to solve
15 min
Success Rate
85%

Problem Statement
Suggest Edit

You have been given two integers ‘X’ and ‘Y’ which are the first two integers of a series and an integer ‘N’. You have to find the Nth number of the series using the Fibonacci rule given by f(x) = f(x-1) + f(x-2).

The answer may be very large, return it after modulus 10^9+7.

Note: The series is 1-based indexed.

Input Format:
The first line contains an integer T denoting the number of test cases. Then each test case follows.

The first line of each test case contains three space-separated integers ‘X’,’Y’ and ‘N’, respectively.

‘X’ and ‘Y’ represent the first and second element of the series while N represents which number of the sequence we have to find out.
Output Format:
For each test case, the only line of output will print the Nth number of the series.

Print output of each test case in separate lines.

Note: You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 100
1 <= N <= 10^18
-10^6 <= X,Y <= 10^6

Time limit:1 sec
Sample Input 1:
2
2 3 4
-1 -2 1
Sample output 1:
8
1000000006
Explanation of Sample output 1:
For the first test case, the series will be 2, 3, 5, 8, 13. So the 4th element will be 8.

For the second test case, the series will be -1, -2, -3, -5, -8. So, the 1st element will be -1. As we are supposed to modulate this with 10^9 + 7, we will get 1000000006.
Sample Input 2:
1
2 3 4
Sample output 2:
8
Want to solve this problem? Login now to get access to solve the problems