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{array}{rl}g(0)& =a\\ g(1)& =b\\ g(n)& =g(n-1)+g(n-2),2\le n\in \mathbb{Z}\end{array}}$$

For various Generalized Fibonacci Sequences, Arup would like to know the $n$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 ${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 $n$th 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