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 (1 + β) = (1 + 3) = 2. α2 (1 + β) 1 + (1+β) 1 + 2 • The previous two grades are β and , so the fourth exam gets α = = 2. αβ3 • The procedure continues until he’s done with all exams. More formally, we can define the grade Qn of the n-th exam with a recurrence like this: if n=0 if n=1 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 Qn. 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α,βandnonasingleline(1≤α,β≤109 and0≤n≤1015). The last line of the input contains three zeros and should not be processed. Output For each test case, write the value of Qn in a single line. The input will be such that the value of Qn is always an integer. Furthermore, Qi will never be zero for 0 ≤ i ≤ n (in other words, division by zero will never arise when evaluating the recurrence). α Qn= β 1+Qn−1 Qn−2
2/2 Sample Input 110 121 592 233 744 2109 650790 344341899059516 45861686 57 594261603792314 2309734 21045930 808597262407955 000 Sample Output 1 2 2 1 2 650790 804591 2309734