提供一个不超纲的$O(\log n)$做法。

构造方程$a^{2}=a+1$，则有：

$a^{3}=a^{2}+a=2a+1$

$a^{4}=a^{3}+a^{2}=3a+2$

$a^{5}=a^{4}+a^{3}=5a+3$

$a^{6}=a^{5}+a^{4}=8a+5$

……

故$a^{n}=f(n)a+f(n-1)$（这部分想要严谨证明可以使用数学归纳法）

所以我们只需要构造$a^{n}=pa+q$，即可求出$f(n)=p$。

由$a^{n}$的性质，显然有：

$a^{2n}=(a^{n})^{2}=(f(n)a+f(n-1))^{2}=f(n)^{2}a^{2}+2f(n)f(n-1)a+f(n-1)^{2}=(f(n)^{2}+2f(n)f(n-1))a+f(n)^{2}+f(n-1)^{2}$

因此我们可以由$a^{n}$$O(1)$求出$a^{2n}$（以及$a^{2n+1}$）。

所以我们便能使用快速幂递归求解，时间复杂度$O(\log n)$。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, p;
struct node
{
	int a, b;
};
node operator*(node x, node y)
{
	int p1 = x.a * y.a, p2 = x.a * y.b + x.b * y.a, p3 = x.b * y.b;
	return node{(p2 + p1) % p, (p3 + p1) % p};
}
node f(int x)
{
	if (x == 1)
	{
		return node{1, 0};
	}
	node c = f(x >> 1);
	if (x & 1)
	{
		return c * c * f(1);
	}
	return c * c;
}
signed main()
{
	cin >> n >> p;
	cout << f(n).a << endl;
}

快速幂和多项式乘法应该不算超纲吧。
赛后发现很多人都用的矩阵快速幂，但是我不会呀。

前$8$个点没什么好说的。

对于$n\leq 10^9$，我们只需要一个小常数做法，此处注意到取模运算只是在加法后进行，所以可以直接先相加，如果加后答案大于等于$P$，减去$P$即可，比取模快多了。

对于$P\leq 1000$，我们记录相邻两项的$f_i,f_{i+1}$，显然最多模拟$P^2$项以后就会进入周期，我们记录周期的大小即可快速计算。

对于$n\leq 10^{12}$，我们可以先行模拟，比如$f_3=f_1+f_2$，$f_4=f_3+f_2=f_1+2f_2$，$f_5=f_4+f_3=2f_1+3f_2$，看看$f[1000000]=?f[1]+?f[2]$，把这两个问号求出来。 那么显然，对于任意的$i$，都有$f[i]=?f[i-999999]+?f[i-999998]$。

就可以每次$O(1)$的得到$10^6$以后的项了，后续细节不表。

#include<bits/stdc++.h>
#define ll long long
#define maxn 1000005
using namespace std;
ll n,P;
ll f1[maxn],f2[maxn];
int main()
{
	cin>>n>>P;
	f1[1]=1; f2[2]=1;
	for (int i=3;i<=1000000;i++)
	{
		f1[i]=(f1[i-1]+f1[i-2])%P;
		f2[i]=(f2[i-1]+f2[i-2])%P;
	}
	ll now=1,x1=1,x2=1;
	while (now+999998<=n)
	{
		ll n1,n2;
		n1=(f1[999999]*x1+f2[999999]*x2)%P;
		n2=(f1[1000000]*x1+f2[1000000]*x2)%P;
		x1=n1; x2=n2; now+=999998; 
	}
	while (now<n)
	{
		ll y=(x1+x2)%P;
		x1=x2; x2=y; now++;
	}
	cout<<x1<<endl;
}

此外看到了赛时除了超纲做法《矩阵快速幂》以外的其他做法，欢迎在题解区发表。