大家都知道 Fibonacci 数列吧，f1=1,f2=1,f3=2,f4=3,…,fn=fn−1+fn−2

现在问题很简单，输入 n 和 m，求 fn 的前 n 项和 Sn%m。

输入格式

共一行，包含两个整数 n 和 m。

输出格式

输出前 nn 项和 Sn%m 的值。

数据范围

1≤n≤2000000000
1≤m≤1000000010

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 3;

int n, mod;

// 实现矩阵乘法
vector<vector<LL>> mul(vector<vector<LL>>& a, vector<vector<LL>>& b){
    int n = a.size();
    int m = b[0].size();
    int t = b.size();
    vector<vector<LL>> c(n, vector<LL>(m, 0));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            for(int k = 0; k < t; k++){
                c[i][j] = (c[i][j] + a[i][k] * b[k][j] % mod) % mod;
            }
        }
    }
    return c;
}

// 矩阵快速幂
vector<vector<LL>> qmi(vector<vector<LL>>& a, LL k){
    // 单位矩阵I
    vector<vector<LL>> I{{1, 0, 0},
                         {0, 1, 0},
                         {0, 0, 1}
    };
    while(k){
        if(k & 1) I = mul(I, a);
        a = mul(a, a);
        k >>= 1;
        }
    return I;
}


int main() {
    cin >> n >> mod;
    if(n == 1 || n == 2) return 1 % mod;
    n -= 2;
    vector<vector<LL>> A {{1, 0, 0},
                          {1, 1, 1},
                          {1, 1, 0}};

    vector<vector<LL>> ans = qmi(A, n);
    cout << (2 * ans[0][0] + ans[1][0] + ans[2][0]) % mod << endl;
    return 0;
}