update on 2024/12/14，修复了一处笔误。

好厉害的题，怎么场切了那么多，是人吗是人吗。

下文中 $n$ 表示序列长度，$m$ 表示模数，$res$ 指余数，就是原题面中的 $n$。

从一个个的部分分入手。

一、$m$ 为质数

1. $res=0$：因为值域是 $[0,m-1]$，所以只有这 $n$ 个数中出现了 $0$ 才成立，简单容斥，方案数为 $m^{n}-m^{n-1}$。
2. $res\ne 0$：前 $n-1$ 个可以任选非零的数，记 $sum=\prod_{i=1}^{n-1}A_i$，只要最后一个取 $\frac{res}{sum}$ 就可以了，方案数为 $(m-1)^{n-1}$。

二、$m=p^{x}$，其中 $p$ 为质数

1. $res=0$：将每个 $A_i$ 都拆分成 $a \times p^{y}$ 的形式，因为 $\prod_{i=1}^{n}A_i \equiv res \pmod{m}$，$\sum y$ 需要大于等于 $x$。那么单个数的方案数就是 $\frac{m}{p^{y}}$ 再减去 $a$ 为 $p$ 倍数的方案数，化一下式子：

$$\frac{m}{p^{y}}-\frac{m}{p^{y} \times p}=p^{x-y}-p^{x-y-1}=p^{x-y-1} \times (p-1)$$

考虑 $\sum y=t$ 的时候的方案数怎么求，使用隔板法，相当于在 $n+t-1$ 个数中间插入 $n-1$ 个隔板，方案数为 $(_{n-1}^{n+t-1})=(_{t}^{n+t-1})$。容斥掉不合法的情况，总方案数为：

$$m^{n}-\sum_{i=0}^{x-1}(_{i}^{n+i-1})\times p^{xn-i-n} \times (p-1)^n$$

3. $res \ne 0$：将 $res$ 拆分成 $z \times p^{y}$ 的形式，此时成立条件为所有 $A_i$ 的 $p$ 的次数和为 $y$，隔板法是简单的，方案数为 $(_{y}^{n+y-1})$，对于 $z$ 的限制需要用最后一个数调整，可以证明最后一个数一定存在唯一的合法取值，就在原基础上再减去最后一个数的方案数。单个数的方案数不变，这部分的答案是：

$$(_{y}^{n+y-1}) \times p^{xn-y-n} \times (p-1)^n \times \frac{1}{p^{x-y-1} \times (p-1)}=(_{y}^{n+y-1}) \times p^{xn-x-n+1} \times (p-1)^{n-1}$$

三、无特殊性质

对 $m$ 分解质因数后可以变成很多个形如 $\prod_{i=1}^{n}A_i \equiv res \pmod{p^{x}}$ 的小问题，每个小问题的方案数互不影响，总方案数就是小问题的方案数乘起来。

然后你就做完啦！

AC code：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
int n,res,m,ny,cnt,X[100],P[100];
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int quick_pow(int a,int b){
    a%=mod;
    int ans=1;
    while(b>0){
        if(b%2==0)(a*=a)%=mod,b/=2;
        else (ans*=a)%=mod,b--;
    }
    return ans;
}
int C(int n,int m){
    if(m==0)return 1;
    int t=n;
    for(int i=n-1;i>n-m;i--)t=t*i%mod;
    for(int i=1;i<=m;i++)t=t*quick_pow(i,mod-2)%mod;
    return t;
}
signed main(){
    n=read(),res=read(),m=read();
    int ans=1;
    for(int i=2;i*i<=m;i++){
        if(m%i==0){
            P[++cnt]=i;
            while(m%i==0)m/=i,X[cnt]++;
        }
    }
    if(m!=1){
        P[++cnt]=m;
        X[cnt]=1;
    }
    for(int j=1;j<=cnt;j++){
        int p=P[j],x=X[j],temp=0;
        m=1;
        for(int i=1;i<=x;i++)m*=p;
        int result=res%m;
        if(result==0){
            temp=quick_pow(m,n);
            for(int i=0;i<x;i++){
                temp=(temp-C(n+i-1,i)*quick_pow(p,x*n-i-n)%mod*quick_pow(p-1,n)%mod+mod)%mod;
            }
        }
        else{
            int y=0;
            while(result%p==0)result/=p,y++;
            temp=C(n+y-1,y)%mod*quick_pow(p,x*n-x-n+1)%mod*quick_pow(p-1,n-1)%mod;
        }
        (ans*=temp)%=mod;
    }
    cout<<ans;
    return 0;
}