rt，一开始是精度的问题，结果改成 long double 后还是 WA。

#include <cmath>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 3, M = 20;
typedef unsigned long long ll;

ll n;
int m;

struct Matrix{
    ll mar[N][N];
    Matrix() {memset(mar, 0, sizeof mar);}
    void init() {mar[0][0] = mar[1][1] = mar[2][2] = 1;}
    Matrix operator *(const Matrix &o) const{
        Matrix res;
        for(int i = 0; i < N; i++)
            for(int j = 0; j < N; j++)
                for(int k = 0; k < N; k++)
                    res.mar[i][j] = (res.mar[i][j] + (__int128)mar[i][k] % m * o.mar[k][j] % m) % m;
        return res;
    }
}A, res;
ll power10[M];

Matrix qpow(Matrix a, ll b) {
    Matrix res;
    res.init();
    while(b) {
        if(b & 1) res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

int main() {
    scanf("%llu%d", &n, &m);
    power10[0] = 1;
    for(int i = 1; i <= 18; i++)
        power10[i] = power10[i - 1] * 10;
    int limit = (int)log10((long double)n);
    res.mar[0][0] = res.mar[0][2] = 1, res.mar[0][1] = 2;

    A.mar[0][0] = 10, A.mar[0][1] = 0, A.mar[0][2] = 0;
    A.mar[1][0] = 1, A.mar[1][1] = 1, A.mar[1][2] = 0;
    A.mar[2][0] = 0, A.mar[2][1] = 1, A.mar[2][2] = 1;

    for(int i = 0; i < limit; i++) {
        res = res * qpow(A, power10[i + 1] - power10[i] - 1);
        A.mar[0][0] = power10[i + 2] % m;
        res = res * A;
    }

    res = res * qpow(A, n - power10[limit]);

    printf("%llu\n", res.mar[0][0]);
    return 0;
}
/*
99999999999999999 1000000000
*/