Summer Institute '17 Contest 1 P5 - Crazy Math

View as PDF

Submit solution

Points: 15
Time limit: 1.4s
Memory limit: 256M

Problem type
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 a and b are constants:

\displaystyle \begin{align}
g(0) &= a \\
g(1) &= b \\
g(n) &= g(n-1) + g(n-2), 2 \le n \in \mathbb Z
\end{align}

For various Generalized Fibonacci Sequences, Arup would like to know the nth 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 10^9.

Input Specification

The input consists of three non-negative, space separated integers: a (a \le 100), b (b \le 100), and n (n \le 2^{48}), 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.

Output Specification

The output will be a single integer, the nth Generalized Fibonacci number MOD 10^9, corresponding to the input.

Sample Input 1

3 4 1

Sample Output 1

4

Sample Input 2

17 6 2

Sample Output 2

23

Sample Input 3

1 1 3749999997

Sample Output 3

499999999

Comments

There are no comments at the moment.