U254359 ゴージャスドリームス

zqacは、花と緑と子供たちの遊ぶ素敵な世界とAK IOIのBen ccqzに来ました。 赤い花、緑の芝生、遊ぶ子供たち、AK IOIのベンccqzなどがあったが、最も目を引いたのは、広場を囲む緑の円形庭園であった。

zqacは、魔法の関数 $f$ を考え出した思想家である。 $f(1)=x$，$f(2) = y$，$f(x) = f(x-1)+f(x+1)$。求 $f(n)$。 $1\le n\le 10^9$。

正整数 $n$ を1個並べたもの。 次に、2つの整数 $x$, $y$ を持つ線がある。

$f(n)$ の値を出力せよ。

$1\le n\le 10^9$。 $1\le x,y\le 10^4$。