問題文
以下,フィボナッチ数列の第 n 項を Fn とする。
与えられた自然数 n に対して,フィボナッチ数列の第1項から第 n 項までの平方和 Sn を出力せよ。
すなわち,
Sn=F12+F22+⋯+Fn2
を出力すればよい。
ただし,必要であれば問題「フィボナッチ数列の性質①」で作成した関数 Fibonacci
を利用しても構わない。
一般に
k=1∑nFk2=Fn×Fn+1
であることが知られている。(下線部は何が入るか考えてみよう)
制約
- 入力はすべて自然数
- 1≦n≦23
入力
入力は以下の形式で標準入力から与えられます。
出力
Sn を以下の形式で出力してください。
サンプル1
F1=1, F2=1, F3=2, F4=3, F5=5, F6=8, F7=13, F8=21なので,
S8=12+12+22+32+52+82+132+212=714
です。
サンプル2