D - Professor Lazy, Ph.D.

Problem D. Professor Lazy, Ph.D.

Professors are very motivated when they have to travel abroad for a conference (of course, if fees are paid by the university), but they don’t have the same attitude when the moment to grade exams arrives.

Professor Lazy, Ph.D., has a particular way to grade exams (and very unfair, by the way). He puts all his exams in a box and then starts getting them out one by one in a totally random fashion. He assigns grade α to the first exam that he gets out of the box, and grade β to the second exam that he gets out of the box. From that point on, he assigns a grade to each of the exams based on the grades of the previous two exams. What he does is that he takes the grade of the immediately previous exam, adds 1 and divides by the grade of the exam before the previous one.

For example, let’s imagine that α = 2 and β = 3. This is what happens:

The first exam gets α = 2.
The second exam gets β = 3.
The previous two grades are α and β, so the third exam gets = = 2.
The previous two grades are β and , so the fourth exam gets = = 1.
The procedure continues until he’s done with all exams.

More formally, we can define the grade Q_n of the nth exam with a recurrence like this:

Q_n =

(
|| α if n = 0,
|{
β if n = 1,
|||( 1-+-Qn--1
Qn -2 if n ≥ 2.

Even this simple procedure is a lot of work for Professor Lazy, Ph.D., so he asks you to write a program to do it for him. He wants to spend all day long drinking coffee in the cafeteria with other professors. Given α, β and n find the value of Q_n.

Note that the grades do not necessarily lie inside a fixed range. They are just arbitrary integers.

Input

The input contains several test cases (at most 1000). Each test case is described by three integer numbers α, β and n on a single line (1 ≤ α, β ≤ 10⁹ and 0 ≤ n ≤ 10¹⁵).

The last line of the input contains three zeros and should not be processed.

Output

For each test case, write the value of Q_n in a single line. The input will be such that the value of Q_n is always an integer. Furthermore, Q_i will never be zero for 0 ≤ i ≤ n (in other words, division by zero will never arise when evaluating the recurrence).

Sample input and output

standard input	standard output

1 1 0 1 2 1 5 9 2 2 3 3 7 4 4 2109 650790 344341899059516 45861686 57 594261603792314 2309734 21045930 808597262407955 0 0 0	1 2 2 1 2 650790 804591 2309734