矩阵具有结合律，所以求 $F[n] = F[1] * A * A * … * A = F[1] * A ^ n$ ，利用快速幂，下面找出A的表达式

已知：$T[n] = f[1] + 2f[2] + 3f[3] + … + nf[n]$

令$P[n] = nS[n] - T[n] = (n-1)f[1] + (n-2)f[2] + … + f[n-1]$—①，

则$T[n] = nS[n] - P[n]$，求出$S[n]$和$P[n]$即可

$P[n+1] = (n+1)S[n+1] - T[n+1] = nf[1] + (n-1)f[2] + … + 2f[n-1] + f[n]$—②

②-① = $S[n] -> P[n+1] = P[n] + S[n]$，即$P[n] = P[n-1] + S[n-1]$

知道了:
1、$P[n] = P[n-1] + S[n-1]$

2、$S[n] = S[n-1] + f[n]$

3、$f[n] = f[n - 1] + f[n - 2]$

令$ F[n]= \left\[ \begin{matrix} f[n] , f[n+1] , S[n] , P[n] \\\ \end{matrix} \right\] $

令$ F[n+1]= \left\[ \begin{matrix} f[n+1] , f[n+2] , S[n+1] , P[n+1] \\\ \end{matrix} \right\] $

$F[n] * A = F[n + 1]$ ， 利用矩阵乘法的运算法则，求出$A$：

推得
$ A= \left\[ \begin{matrix} 0 & 1 & 0 & 0 \\\ 1 & 1 & 0 & 0 \\\ 0 & 0 & 1 & 1 \\\ 0 & 0 & 1 & 1 \\\ \end{matrix} \right\] $

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;

int n , m;

const int N = 4;

void mul(int a[][4] , int b[][4] , int c[][4])
{
    int temp[4][4] = {0};
    for(int i = 0 ; i < 4 ; i++)
        for(int j = 0 ; j < 4 ; j++)
            for(int k = 0 ; k < 4 ; k++)
                temp[i][j] = (temp[i][j] + (LL)b[i][k] * c[k][j]) % m;

    memcpy(a , temp , sizeof temp);
}

int main()
{
    int a[4][4] = {
        {0 , 1 , 0 , 0},
        {1 , 1 , 1 , 0},
        {0 , 0 , 1 , 1},
        {0 , 0 , 0 , 1}
    };

    int f[4][4] = {1 , 1 , 1 , 0};

    cin >> n >> m;

    int k = n - 1;

    while(k)
    {
        if(k & 1) mul(f , f , a);
        mul(a , a, a);
        k >>= 1;
    }

    cout << (((LL)n * f[0][2] - f[0][3]) % m + m) % m << endl; 
    return 0;
}