Summer Institute @ University of Central Florida: Contest 1, Problem 5
Arup loves math. Many love the Fibonacci sequence, but true mathematicians love to generalize results. As such, Arup prefers looking at the Generalized Fibonacci Sequence that is defined as follows, where and are constants:
For various Generalized Fibonacci Sequences, Arup would like to know the th term of the sequence. Can you write a program to do it for him? Additionally, since Generalized Fibonacci numbers get very big quickly, Arup would like you to calculate the final result MOD .
The input consists of three non-negative, space separated integers: , , and , the first term of the Generalized Fibonacci sequence, the second term of the Generalized Fibonacci sequence and the Generalized Fibonacci number Arup wants you to calculate, respectively.
The output will be a single integer, the th Generalized Fibonacci number MOD , corresponding to the input.
Sample Input 1
3 4 1
Sample Output 1
Sample Input 2
17 6 2
Sample Output 2
Sample Input 3
1 1 3749999997
Sample Output 3