题目描述

关于斐波那契数列张三已经了解到不少知识，他发现除了其他方法能够实现精准输出斐波那契数列第几项外，利用倍增法似乎也能完成。请你帮助他设计一个倍增法输出斐波那契数列的程序。

输入格式

输入一个数，表示需要输出第几项斐波那契数的值。

输出格式

输出该项的斐波那契数值

样例

输入样例 1

9

输出样例 1

F(9) = 34

输入样例 2

0

输出样例 2

F(0) = 0

输入样例 3

15

输出样例 3

F(15) = 610