zyy 的模拟赛 森破

题面

大头会求 ，其中 。

大头觉得这题实在是图样图森破。

他想了想，让他们求 ，可是大头觉得这题实在还是图样图森破。

大头想到这么一道 题:

求 的值

大头现在不觉得这道题图样图森破了，于是他把题目交给了你。

Input

第一行 1 个数 n，含义如题所示

Output

一行一个数，表示答案。

Sample Input

12

Sample Output

75025

题解

模拟赛做到了这题，觉得比较巧妙，于是放出来和大家分享一下。

我想zyy应该不会说什么。。

首先你如果打表的话就会发现答案其实就是

来证明一下。

显然这题要用到二项式定理。

关于二项式定理的证明可以看wiki上的证明，这里就不赘述了。

这个式子是不是和要求的式子很像？

我们再来看看求斐波那契第 项的做法：

设

于是我们可以得出以下结论

用单位矩阵 代替，那么答案就是

注意到 就是 ，所以答案就是

代码就不用了吧。。