容易想到放到prufer序列上，变成下面的形式。
\(\sum\limits_{\sum c_i=n-2}{\frac{(n-2)!}{\prod\limits_{i=1}^{n}{c_i!}}\prod\limits_{i=1}^{n}{a_i^{c_i+1}(c_i+1)^m}\sum\limits_{i=1}^{n}{(c_i+1)^m}}\)
\(=(n-2)!\prod\limits_{i=1}^n{a_i}\sum\limits_{\sum c_i=n-2}{\prod\limits_{i=1}^n{\frac{a_i^{c_i+1}(c_i+1)^m}{c_i!}}\sum\limits_{i=1}^{n}{(c_i+1)^m}}\)
设\(A_x(x)=\sum\limits_{i=0}^{\infty}{\frac{a_x^i(i+1)^m}{i!}[x_n]},B_x(x)=\sum\limits_{i=0}^{\infty}{\frac{a_x^i(i+1)^{2m}}{i!}[x_n]}\)
即求\(\sum\limits_{i=1}^{n}{B_i(x)\prod\limits_{j\not =i}{A_j(x)}}\)
\(=\sum\limits_{i=1}^{n}{\frac{B_i(x)}{A_i(x)}}\prod\limits_{i=1}^{n}{A_i(x)}\)
\(=\sum\limits{\frac{B_i(x)}{A_i(x)}}\exp \sum\limits_{i=1}^{n}{\ln A_i(x)}\)
问题即为求\(f_i=\sum\limits_{j=1}^{n}{(a_j)^i}\)虽然暴力能过
生成函数为\(\frac{1}{1-a_ix}\)
\(\sum\limits{\frac{1}{1-a_ix}}=\frac{\sum\limits_{i=1}^n{\prod\limits_{j\not =i}{1-a_jx}}}{\prod{1-a_ix}}\)
设上面为\(P(x)=\sum\limits_{i=0}^{\infty}{p_ix^i}\)，下面为\(Q_i=\sum\limits_{i=0}^{\infty}{q_ixi}\)。
对比系数以后可得\(q_i(n-i)=p_i\)，则分治+NTT乘出\(Q\)即可。
时间复杂度\(O(n\log ^2n)\)
code:
#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n))
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned ll;
using namespace std;const int N=(1<<16)+5,M=170+5,K=1e5+5,mod=998244353,Mod=mod-1;const ll INF=1e18+7;const db eps=1e-5;mt19937 rnd(time(0));
int n,m,k,x,y,z;ll A[N],B[N],C[N],frc[N],Inv[N],D[N],f[N];
ll mpow(ll x,int y=mod-2){ll Ans=1;while(y) y&1&&(Ans=Ans*x%mod),y>>=1,x=x*x%mod;return Ans;}
namespace Poly{const int G=3,Ig=mpow(G);
int tr[N];ll C[N],D[N],f[N],g[N],H[N];
void Init(int n){for(k=1;k<=2*n;k<<=1);for(int i=0;i<k;i++) tr[i]=(tr[i>>1]>>1)|((i&1)?k/2:0);}
void NTT(ll *A,int k,int Fl){
int i,j,h;ll key,now,pus;for(i=0;i<k;i++) tr[i]<i&&(swap(A[i],A[tr[i]]),0);
for(i=2;i<=k;i<<=1){
for(key=mpow(Fl?G:Ig,(mod-1)/i),j=0;j<k;j+=i){
for(now=1,h=j;h<j+i/2;h++) pus=now*A[h+i/2]%mod,A[h+i/2]=(A[h]-pus+mod)%mod,A[h]=(A[h]+pus)%mod,now=now*key%mod;
}
}if(Fl) return;ll Iv=mpow(k);for(i=0;i<k;i++) A[i]=A[i]*Iv%mod;
}
void Inv(ll *A,ll *B,int n){
if(n==1){B[0]=mpow(A[0]);return;}Inv(A,B,n+1>>1);int i;Init(n);for(i=0;i<n;i++) C[i]=A[i],D[i]=B[i];
NTT(C,k,1);NTT(D,k,1);for(i=0;i<k;i++) C[i]=D[i]*(2+mod-C[i]*D[i]%mod)%mod;NTT(C,k,0);for(i=0;i<n;i++) B[i]=C[i];
for(i=0;i<k;i++) C[i]=D[i]=0;
}
void Ln(ll *A,ll *B,int n){
int i;Inv(A,f,n);Init(n);for(i=0;i<n;i++) g[i]=A[i+1]*(i+1)%mod;NTT(f,k,1);NTT(g,k,1);for(i=0;i<k;i++) f[i]=f[i]*g[i]%mod;NTT(f,k,0);
B[0]=0;for(i=1;i<n;i++) B[i]=f[i-1]*mpow(i)%mod;for(i=0;i<k;i++) g[i]=f[i]=0;
}
void Exp(ll *A,ll *B,int n){
if(n==1){B[0]=1;return;}Exp(A,B,n+1>>1);int i;Ln(B,H,n);for(i=0;i<n;i++) H[i]=((!i)+mod+A[i]-H[i])%mod;
Init(n);for(i=0;i<n;i++) C[i]=B[i];NTT(H,k,1);NTT(C,k,1);
for(i=0;i<k;i++) C[i]=C[i]*H[i]%mod;NTT(C,k,0);for(i=0;i<n;i++) B[i]=C[i];for(i=0;i<k;i++) C[i]=H[i]=0;
}
void calc(ll *A,int l,int r){
if(l==r) return;int i,m=l+r>>1;calc(A,l,m);calc(A,m+1,r);Init(r-l+1);
for(i=2*l-2;i<=2*m-1;i++) C[i-2*l+2]=A[i];for(i=2*(m+1)-2;i<=2*r-1;i++) D[i-(2*(m+1)-2)]=A[i];
NTT(C,k,1);NTT(D,k,1);for(i=0;i<k;i++) C[i]=C[i]*D[i]%mod;NTT(C,k,0);for(i=2*l-2;i<=2*r-1;i++) A[i]=C[i-2*l+2];
for(i=0;i<k;i++) C[i]=D[i]=0;
}
}
int main(){
int i,j;scanf("%d%d",&n,&m);for(i=1;i<=n;i++) scanf("%lld",&C[i]);
for(frc[0]=Inv[0]=i=1;i<=n;i++) frc[i]=frc[i-1]*i%mod,Inv[i]=mpow(frc[i]);
for(i=1;i<=n;i++) D[2*i-2]=1,D[2*i-1]=mod-C[i];Poly::calc(D,1,n);D[n]=0;for(i=0;i<n;i++) A[i]=D[i]*(n-i)%mod;
Poly::Inv(D,f,n);Poly::Init(n);Poly::NTT(f,k,1);Poly::NTT(A,k,1);for(i=0;i<k;i++) f[i]=f[i]*A[i]%mod;Poly::NTT(f,k,0);
for(i=0;i<k;i++) D[i]=A[i]=0;
for(i=0;i<n;i++) A[i]=mpow(i+1,m)*Inv[i]%mod,B[i]=mpow(i+1,2*m)*Inv[i]%mod;
Poly::Inv(A,D,n);Poly::Init(n);Poly::NTT(B,k,1);Poly::NTT(D,k,1);for(i=0;i<k;i++) B[i]=B[i]*D[i]%mod;Poly::NTT(B,k,0);for(i=n;i<k;i++) B[i]=0;
Me(D,0);Poly::Ln(A,D,n);for(i=0;i<n;i++) D[i]=D[i]*f[i]%mod,B[i]=B[i]*f[i]%mod;Me(A,0);Poly::Exp(D,A,n);
Poly::Init(n);Poly::NTT(B,k,1);Poly::NTT(A,k,1);for(i=0;i<k;i++) A[i]=A[i]*B[i]%mod;Poly::NTT(A,k,0);
ll Ans=A[n-2];for(i=1;i<=n;i++) Ans=Ans*C[i]%mod;printf("%lld\n",Ans*frc[n-2]%mod);
}