Description

小 C 数学成绩优异, 于是老师给小 C 留了一道非常难的数学作业题:

给定正整数 \(n, m\), 要求计算 \(concatenate(1 \ldots n) \bmod m\) 的值, 其中 \(concatenate(1 \ldots n)\) 是将所有正整数 \(1, 2, \ldots n\) 顺序连接起来得到的数. 例如,\(n = 13\), 则 \(concatenate(1 \ldots n) = 12345678910111213\).

小 C 想了大半天终于意识到这是一道不可能手算出来的题目, 于是他只好向你求助, 希望你能编写一个程序帮他解决这个问题.

Input

输入文件只有一行且为用空格隔开的两个正整数 \(n, m\).

Output

输出仅包含一个非负整数, 表示 \(concatenate(1 \ldots n) \bmod m\) 的值.

Sample Input

12345678910 1000000000

Sample Output

345678910

Data Range

对于所有的数据, 满足:\(1 \leq n \leq 10^{18}, 1 \leq m \leq 10^9\).

Explanation

首先考虑 \(O(n)\) 的做法, 我们发现这个实在是太有规律了, 因为每一次都可以用上一次的结果来进行动规, 所以完全只依赖于上一个结果. 虽然对于 \(10^{18}\) 的数据无法通过, 但是拥有了这个性质,\(O(\log n)\) 的做法就比较显然了.

我们可以构造矩阵来进行优化, 具体地来说, 做法是这样的: 考虑答案矩阵 \(A\), 我们将 \(n\) 分成若干段, 这些段上每一段对应的数字在十进制中位数都应该相同. 得到了这个性质, 我们便需要对每一段进行矩阵乘法.

我们记每一次的位数为 \(t\), 则相应地, 答案矩阵的计算方法为:\[ A = \prod_{t=1}^{\left\lfloor \lg n \right\rfloor} \begin{bmatrix} 10^t & 0 & 0\\ 1 & 1 & 0\\ 1 & 1 & 1 \end{bmatrix}^{9 \times 10^{t-1}} \cdot \begin{bmatrix} 10^{\left\lfloor \lg n \right\rfloor + 1} & 0 & 0\\ 1 & 1 & 0\\ 1 & 1 & 1 \end{bmatrix}^{n - \left\lfloor \lg n \right\rfloor + 1} \] 中间可能有一些东西不是特别好推, 但是递推迭代时候比在公式里好写......

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>

using namespace std;
typedef long long lli;
/* const */ lli modr = 1000000007;

lli mul(lli a, lli b)
{
    lli c = 0;
    for (; b > 0; a = (a + a) % modr, b >>= 1)
        if (b & 1) c = (c + a) % modr;
    return c;
}

struct matrix {
    lli dat[4][4];
    matrix(void) {
        memset(dat, 0, sizeof(dat)); }
    matrix(lli v) { memset(dat, 0, sizeof(dat));
        dat[1][1] = dat[2][2] = dat[3][3] = v; }
    matrix(lli _1, lli _2, lli _3, lli _4, lli _5, lli _6, lli _7, lli _8, lli _9) {
        dat[1][1] = _1 % modr, dat[1][2] = _2 % modr, dat[1][3] = _3 % modr;
        dat[2][1] = _4 % modr, dat[2][2] = _5 % modr, dat[2][3] = _6 % modr;
        dat[3][1] = _7 % modr, dat[3][2] = _8 % modr, dat[3][3] = _9 % modr; }
    lli* operator[] (int x) {
        return dat[x]; }
    void print(void) {
        printf("[ %lld\t%lld\t%lld ]\n| %lld\t%lld\t%lld |\n[ %lld\t%lld\t%lld ]\n\n",
        dat[1][1], dat[1][2], dat[1][3], dat[2][1], dat[2][2], dat[2][3],
        dat[3][1], dat[3][2], dat[3][3]); }
}; matrix operator * (matrix a, matrix b) {
    matrix c;
    for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= 3; j++) {
            c[i][j] = 0;
            for (int k = 1; k <= 3; k++)
                c[i][j] = (c[i][j] + mul(a[i][k], b[k][j])) % modr;
        }
    return c;
} matrix operator + (matrix a, matrix b) {
    matrix c;
    for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= 3; j++)
            c[i][j] = (a[i][j] + b[i][j]) % modr;
    return c;
} matrix qpow(matrix a, lli b) {
    matrix c(1);
    for (; b > 0; a = a * a, b >>= 1) {
        if (b & 1)
            c = c * a;
    }
    return c;
}

matrix work(matrix a, lli t, lli n)
{
    matrix b(
        t, 0, 0,
        1, 1, 0,
        1, 1, 1);
    a = a * qpow(b, n - t/10 + 1);
    return a;
}

lli n;

int main(int argc, char** argv)
{
    scanf("%lld%lld", &n, &modr);
    matrix a(1);
    lli t = 10;
    while (n >= t) {
        a = work(a, t, t - 1);
        t *= 10;
    }
    a = work(a, t, n);
    lli res = a[3][1];
    printf("%lld\n", res);
    return 0;
}