答案结论：$(n+1) \times S_n - G_n$，其中$S_n$是数列$\{F_n\}$的前缀和，$G_n$是$S_n$的前缀和。

代码实现：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL P;
struct node
{
    LL a[5][5];
    node(){memset(a,0,sizeof a);}
};

node operator*(node A,node B) {
    node C; 
    for (int i=1;i<=4;i++)
        for (int j=1;j<=4;j++)
            for (int k=1;k<=4;k++)
                C.a[i][j]=(C.a[i][j]+ A.a[i][k]*B.a[k][j])%P;
    return C;
}
node qpow(node A,int b) {
    node C;for(int i=1;i<=4;i++)C.a[i][i]=1;
    for(;b;b>>=1) {
        if(b&1)C=C*A; 
        A=A*A;
    }
    return C;
}
int main() {
    LL n;scanf("%lld%lld",&n,&P);
    node A;//A的第一行(Fn-1, Fn, Sn, Gn) ，Sn是Fn的前缀和，Gn是sn的前缀和 
    //答案为 (n+1)*Sn - Gn ，此题模型较为常见，技巧需要推广 
    A.a[1][1]=0;A.a[1][2]=1;A.a[1][3]=1;A.a[1][4]=1;
    node ff;
    ff.a[1][1]=0;
    ff.a[2][1]=1;
    ff.a[1][2]=1;
    ff.a[2][2]=1;
    ff.a[1][3]=

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL P;
struct node
{
    LL a[5][5];
    node(){memset(a,0,sizeof a);}
};

node operator*(node A,node B)
{
    node C; 
    for (int i=1;i<=4;i++)
        for (int j=1;j<=4;j++)
			for (int k=1;k<=4;k++)
                C.a[i][j]=(C.a[i][j]+ A.a[i][k]*B.a[k][j])%P;
    return C;
}
node qpow(node A,int b)
{
    node C;for(int i=1;i<=4;i++)C.a[i][i]=1;
    for(;b;b>>=1)
    {
        if(b&1)C=C*A; 
        A=A*A;
    }
    return C;
}
int main()
{
    LL n;scanf("%lld%lld",&n,&P);
    node A;//A的第一行(Fn-1,Fn,Sn,Gn) ,Sn是Fn的前缀和，Gn是sn的前缀和 
    //答案为 (n+1)*Sn - Gn ，此题模型较为常见，技巧需要推广 
	A.a[1][1]=0;A.a[1][2]=1;A.a[1][3]=1;A.a[1][4]=1;
    node ff;
    ff.a[1][1]=0;
    ff.a[2][1]=1;
    
    ff.a[1][2]=1;
    ff.a[2][2]=1;
 
    ff.a[1][3]=1;
    ff.a[2][3]=1;
    ff.a[3][3]=1;
    
    ff.a[1][4]=1;
    ff.a[2][4]=1;
    ff.a[3][4]=1;
    ff.a[4][4]=1;
    
    
    A=A*qpow(ff,n-1);
    printf("%lld\n",((n+1)%P*A.a[1][3]%P-A.a[1][4]+P)%P);
    return 0;
}