思路

构建序列$P_n=nS_n-T_n$
求出关于向量$[P_n, S_n, f_{n+1}, f_n]$的状态转移方程，使用矩阵快速幂求解

c++ 构造序列求解

#include <cstring>
#include <iostream>

using namespace std;
typedef long long LL;
const int N=4;
int n, mod;

void mmul(LL c[][N], LL a[][N], LL b[][N]){ // c=a*b
    LL temp[N][N]={0};
    for(int i=0; i<N; ++i)
        for(int j=0; j<N; ++j)
            for(int k=0; k<N; ++k)
                temp[i][j]=(temp[i][j]+a[i][k]*b[k][j])%mod;
    memcpy(c, temp, sizeof temp);
}

int main(){
    cin>>n>>mod;
    LL v[N][N]={
        {0, 0, 0, 0}, //pi
        {1, 0, 0, 0}, //si
        {1, 0, 0, 0}, //f_i+1
        {1, 0, 0, 0}  //fi
    };
    LL A[N][N]={
        {1, 1, 0, 0},
        {0, 1, 1, 0},
        {0, 0, 1, 1},
        {0, 0, 1, 0}
    }; // 转移矩阵
    int k=n;
    n--;
    while(n){
        if(n&0x01) mmul(v, A, v);
        mmul(A, A, A);
        n>>=1;
    }
    cout<<((v[1][0]*k-v[0][0])%mod+mod)%mod<<endl;
    return 0;
}