This is the past problem of hackerearth how to solve this

Fibonnaci numbers commonly denoted F form a sequence, called the
Fibonacci sequence, such that each number is the sum of the two
preceding ones, starting from 0 and 1. That is,
F = 0
F = 1
F = F + F , for integer n > 1.
One way of generalizing the Fibonacci sequence is by starting with
any pair of numbers and extending to negative values of n.
Given two terms of a generalized Fibonacci sequence Fp and Fq ,
their positions p and q respectively and a position r , |nd Fr .
Input Format
The |rst line of the input contains an integer t denoting the number
of test cases.
Each test case contains three lines.
First line of each test case contains two space separated
integers p and Fp
Second line contains two space separated integers q and Fq
Third line contains an integer r
Output Format
For each test case, print Fr which is the term of the sequence at
position r .
If Fr is not an integer, represent it as an irreducible fraction in the
form a/b where b > 0.