題目描述

非波林數列（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

其中， a₁ 及 a₂ 為給定的正整數。 你要做的就是對於給定的 a₁，a₂ 及 n, 找出 f(n) 的值。 因 f(n) 的值可能是非常之大，所以只要出輸 f(n) MOD 10⁹ (即 f(n) 除 10⁹ 後的餘數)。

輸入格式

輸入數據中有若干組數，每組均含有三個正整數 a₁ a₂ n。 以一個空格分隔開。 所有輸入的正整數均小於或等於 1,000,000,000。且 n ≥ 3。 最後一個輸入為數 0 0 0 （三個 0），代表輸入的結束。

輸出格式

對應於每組輸入數據，請在一行上輸出對應旳 f(n) MOD 10⁹ 的值。 輸出的答案除 0 外，其他的數值均不可以 0 作為開頭。

Samples

1 1 13
2 3 20
0 0 0

233
17711

提示

#非官方測試數據

原始資料

• Zero1 題號：a334
• Hydro 題號：Z0334
• Locale：zh_TW
• Display：open