非波林數列（Fibonacci Sequence）是一個常見的數列，學過遞歸的學生都應該見過這個數列。 它的定義如下：
f(0) = 0
f(1) = 1
f(n) = f(n-2) + f(n-1) 對於 n ≥ 2
我們現在有另一個類似的函數，其定義如下：
f(1) = a1
f(2) = a2
f(n) = f(n-2) + f(n-1) 對於 n ≥ 3
其中， a1 及 a2 為給定的正整數。 你要做的就是對於給定的 a1，a2 及 n, 找出 f(n) 的值。 因 f(n) 的值可能是非常之大，所以只要出輸 f(n) MOD 109 (即 f(n) 除 109 後的餘數)。
輸入數據中有若干組數，每組均含有三個正整數 a1 a2 n。 以一個空格分隔開。 所有輸入的正整數均小於或等於 1,000,000,000。且 n ≥ 3。 最後一個輸入為數 0 0 0 （三個 0），代表輸入的結束。
對應於每組輸入數據，請在一行上輸出對應旳 f(n) MOD 109 的值。 輸出的答案除 0 外，其他的數值均不可以 0 作為開頭。
1 1 13 2 3 20 0 0 0
233 17711
#非官方測試數據
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||