根据状态转移方程，使用矩阵快速幂求解
$$ \left[ \begin{matrix} s[n]\\ f[n+1]\\ f[n] \end{matrix} \right]= \left[ \begin{matrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 1 & 0 \end{matrix} \right] \times \left[ \begin{matrix} s[n-1] \\ f[n]\\ f[n-1] \end{matrix} \right] $$

c++ Fibo前$n$项和

#include <cstring>
#include <iostream>
#include <functional>

using namespace std;

typedef long long LL;
const int N=3;
int n, mod;

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

void mmul(int c[][N], int a[][N], int b[][N]){ // 矩阵*矩阵
    int 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]+(LL)a[i][k]*b[k][j])%mod;
    memcpy(c, temp, sizeof temp);
}


int main(){
    cin>>n>>mod;
    int v[N]={1, 1, 1}; // s1=f1=f2=1
    int a[N][N]={
        {1, 1, 0},
        {0, 1, 1},
        {0, 1, 0}
    }; // 状态转移矩阵

    function<void()> mprint=[&](){
        for(int i=0; i<N; ++i){
            for(int j=0; j<N; ++j)
                cout<<a[i][j]<<" ";
            cout<<endl;
        }
        cout<<"---------------"<<endl;
    };

    function<void()> vprint=[&](){
        for(int i=0; i<N; ++i) cout<<v[i]<<" ";
        cout<<endl;
        cout<<"~~~~~~~~~~~~~~~~"<<endl;
    };

    // 矩阵快速幂
    // 计算a^n*f
    n--;
    while(n){
        if(n&0x01) vmul(v, a, v);
        mmul(a, a, a);
        n>>=1;
        // vprint();
        // mprint();

    }
    cout<<v[0]<<endl;

}