读了一下题就会很愉快的发现這个数列是关于p的幂次的斐波那契数列，很愉快然后就很愉快的发现可以矩阵快速幂一波，然后再一看数据范围就......然后由于上帝与集合對我的正确启示我就发现这个东西可以用欧拉函数降一下幂，因为两个数一定互质因此不用再加一个phi(m)于是放心的乘吧宝贝！！

如何求得dp[i]呢

我们可以解特征方程（1），得到：

　　求得a和b后再做快速幂。

我们也可以直接用矩阵快速幂来求得***