好像网上没有这么做的题解，所以就写个吧。
直接单位根反演，就有： \[ \frac{1}{k}\sum_{j=0}^{k-1}\sum_{i=0}^n{n \choose i}(\omega_k^j)^iF_i \] 正常的做法是把斐波那契数用矩阵表示，然后用二项式定理。
考虑直接头铁用通项公式展开斐波那契数，就有 \[ \frac{1}{\sqrt{5}k}\sum_{j=0}^{k-1}\left(\frac{1+\sqrt{5}}{2}(1+\frac{1+\sqrt{5}}{2}\omega_k^j)^n-\frac{1-\sqrt{5}}{2}(1+\frac{1-\sqrt{5}}{2}\omega_k^j)^n\right) \] 在模意义下可能没有 \(5\) 的二次剩余，故考虑扩域，把数表示成 \(a+b\sqrt{5}\) 的形式。
定义一下扩域后数的加减乘除然后直接做即可。在这里除法的本质是求逆元，也就是求 \(c+d\sqrt{5}\) 使得它和 \(a+b\sqrt{5}\) 乘起来为 \(1\)。
不过需要注意的是，当 \(P=5\) 的时候，\(\frac{1}{\sqrt{5}k}\) 没有逆元，这样就会 WA，考虑特殊处理一下。
可以发现 \(\frac{1}{\sqrt{5}k}\) 表示成 \(a+b\sqrt{5}\) 的形式的时候 \(a=0\)，那么当 \(P\not=5\) 的时候它的逆元 \(a=0\)，既然这样，后面的式子求出来的 \(a\) 也会等于 \(0\)。
所以我们根本没有必要在这一步把这个复数求逆，直接把 \(k\) 求逆乘上后面的式子求出来的 \(b\) 即可。
常数可能会比矩阵乘法的做法小。