rt，第二个样例过不去

想法是把贡献展开算。

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

#define LL long long
#define MOD 998244353

using namespace std;
LL n; int m,a[25][25];

int pcnt,p[25],vis[25];

void euler() {
    for (int i=2;i<=m;i++) {
        if (!vis[i]) p[++pcnt]=i;
        for (int j=1;j<=pcnt and i*p[j]<=m;j++) {
            vis[i*p[j]]=1;
            if (i%p[j]==0) break;
        }
    }
}

struct Matrix {
    LL a[64][64];

    Matrix() { memset(a,0,sizeof a); }
    LL *operator[](int x) { return a[x]; }
    Matrix operator*(Matrix &B) {
        Matrix C;
        for (int i=0;i<(1<<pcnt);i++)
            for (int j=0;j<(1<<pcnt);j++)
                for (int k=0;k<(1<<pcnt);k++)
                    (C[i][j]+=a[i][k]*B[k][j]%MOD)%=MOD;
        return C;
    }
}A,E;

Matrix quickpow(Matrix &a,LL k) {
    Matrix res; for (int i=0;i<(1<<pcnt);i++) res[i][i]=1;
    while (k) {
        if (k&1) res=res*a;
        a=a*a,k>>=1;
    }
    return res;
}

int main() {
    scanf("%lld%d",&n,&m);
    euler();
    for (int i=1;i<=m;i++) {
        int tmp=i;
        for (int j=1;j<=pcnt;j++)
            if (tmp%p[j]==0)
                while (tmp%p[j]==0) a[i][j]++,tmp/=p[j];
    }
    for (int i=1;i<=m;i++) {
        for (int j=0;j<(1<<pcnt);j++) {
            for (int k=0;k<(1<<pcnt);k++) {
                bool flag=0;
                for (int l=1;l<=pcnt;l++)
                    if (((j>>(l-1))&1) and ((k>>(l-1))&1)==0) { flag=1; break; }
                if (flag) continue;
                LL mul=1;
                for (int l=1;l<=pcnt;l++)
                    if (((j>>(l-1))&1)==0 and ((k>>(l-1))&1))
                        mul=mul*a[i][l]%MOD;
                (A[j][k]+=mul)%=MOD;
            }
        }
    }
    for (int i=0;i<(1<<pcnt);i++) E[0][i]=1;
    A=quickpow(A,n); E=E*A;
    printf("%lld\n",E[0][(1<<pcnt)-1]);
    return 0;
}