フィボナッチ数列の性質②

2 secs 1024 MB
Aozora_Kotori_A

問題文


以下,フィボナッチ数列の第 項を とする。

与えられた自然数 に対して,フィボナッチ数列の第1項から第 項までの平方和 を出力せよ。

すなわち,

を出力すればよい。 ただし,必要であれば問題「フィボナッチ数列の性質①」で作成した関数 Fibonacci を利用しても構わない。

一般に

であることが知られている。(下線部は何が入るか考えてみよう)

制約


  • 入力はすべて自然数

 

入力


入力は以下の形式で標準入力から与えられます。

標準入力

出力


を以下の形式で出力してください。

標準出力

 

サンプル1

入力
8
出力
714

なので,

です。

 

サンプル2

入力
18
出力
10803704

提出


Go (1.14)