该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

众所周知，小狐芦擅长计算，尤其擅长计算组合数，然而这道题和组合数并没有什么关系。

今天小狐芦学习了斐波那契数列，矩阵乘法和快速幂的原理，觉得很有趣，他觉得可以将他们组合起来使斐波那契数列某一项的值更迅速的求解，但是他并不知道如何操作，于是找到了无所不能的你，请你来帮他解决这个问题。

补充：

1. 关于斐波那契：

   斐波那契数列，又称黄金分割数列，因数学家莱昂纳多·斐波那契以兔子繁殖为例子而引入，故又称“兔子数列”，其数值为： $1、1、2、3、5、8、13、21、34 \cdots$ 在数学上，这一数列以如下递推的方法定义： $F(1)=1,F(2)=1,F(n)=F(n - 1)+F(n - 2)(n \ge 3,n \in N)$ 。

2. 关于矩阵乘法：

   得到的矩阵的第 $(x,y)$ 个元素的值为第一个矩阵的第 $x$ 行和第二个矩阵的第 $y$ 行对应相乘的和，具体如下。

   

   对于矩阵乘法的模板：

   #include<bits/stdc++.h>
   using namespace std;
   struct mat{
   	long long val[3][3];//2×2的矩阵（使用下表1，2）
   };
   mat mul( mat o, mat p)//返回值为矩阵o × 矩阵p所得到的矩阵
   {
   	mat c;
   	for(int i=1;i<=2;i++)
   		for(int j=1;j<=2;j++)
   			c.val[i][j]=0;
   	for(int i=1;i<=2;i++)
   		for(int j=1;j<=2;j++)
   			for(int k=1;k<=2;k++)
   				c.val[i][j]=(c.val[i][j]+(o.val[i][k]*p.val[k][j]));
   	return c;
   }
   mat a, b, c;
   int main(){
   	a.val[1][1] = 1, a.val[1][2] = 2;
   	a.val[2][1] = 4, a.val[2][2] = 9;
   	/*
   	  a矩阵为：
   	  1 2
   	  4 9
   	 */
   	b.val[1][1] = 5, b.val[1][2] = 7;
   	b.val[2][1] = 2, b.val[2][2] = 0;
   	/*
   	  b矩阵为：
   	  5 7
   	  2 0
   	 */
   	c = mul(a, b);
   	for(int i = 1; i <= 2; i++){
   		for(int j = 1; j <= 2; j++){
   			printf("%lld\t", c.val[i][j]);
   		}
   		printf("\n");
   	}
   }
   

3. 关于快速幂原理：

   本质上就是将指数转化为二进制，然后计算出底数 $x$ 的 $x^{2^0}, x^{2^1}, x^{2^2},\cdots$ ，并将其指数二进制下对应为 $1$ 的位累乘起来从而加速幂运算。

   例：$3^{10} = 3 ^ {(1010)_2} = 3^{(1000)_2} \times 3^{(10)_2} = 6561 \times 9 = 59049$

   对于整数的快速幂代码模板：

   int poww(int a, int b) {
   	int ans = 1, base = a;
   	while (b) {
   		if (b & 1)
   			ans *= base;
   		base *= base;
   		b >>= 1;
   	}
   	return ans;
   }
   

输入

一行一个整数 $n$ 。$(1\le n < 2^{63})$

输出

输出一行一个整数表示斐波那契序列的第 $n$ 个数。

样例

5

5

10

55