首先考虑到这是一张有标号的图，每一个点的地位是相等的，因此我们只需要求出一个点的价值和乘上(n)就好了
考虑一个点有多少种情况下度数为(i)
显然我们可以让除了这个点的剩下的(n-1)个点之间的边随便连，之后这个点从(n-1)个点里选择(i)个连边就好了，于是是(inom{n-1}{i} imes 2^{frac{(n-1)(n-2)}{2}})种情况这个点度数为(i)
我们现在要做的就是这个柿子了
[n2^{frac{(n-1)(n-2)}{2}}sum_{i=0}^{n-1}inom{n-1}{i}i^k
]
我们考虑一下展开(i^k)，自然是用第二类斯特林数了
于是不管前面的，我们要求的东西是
[sum_{i=0}^{n-1}inom{n-1}{i}sum_{j=1}^kS_2(k,j) imes inom{i}{j}j!
]
我们把(j)放到前面来枚举
[sum_{j=1}^kS_2(j,k)j!sum_{i=0}^{n-1}inom{n-1}{i}inom{i}{j}
]
考虑一下(sum_{i=0}^{n-1} inom{n-1}{i}inom{i}{j})的组合意义，就是先从(n-1)里选择了(i)个又从(i)个里选择了(j)个，总体上看是选择了(j)个，是(inom{n-1}{j})种情况，但是我们只需要保证第一次选择的(i)完全包含(j)，显然完全包含(j)的集合有(2^{n-1-j})个
于是我们能把柿子写成这个样子
[sum_{j=1}^kS_2(k,j) imes inom{n-1}{j}2^{n-1-j} imes j!
]
现在的瓶颈在于求第二类斯特林数，我们记得斯特林数有一个容斥写法
[S_2(i,j)=frac{1}{j!}sum_{k=0}(-1)^kinom{j}{k}(j-k)^i
]
我们拆开组合数之后发现这是一个卷积的形式，因此我们可以用(NTT)在(O(nlogn))的时间内卷出一行斯特林数来
于是就解决了
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define re register
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline int read() {
char c=getchar();int x=0;while(c<'0'||x>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
const int maxn=8e5+5;
const int mod=998244353;
const int G[2]={3,332748118};
int rev[maxn],n,k,fac[maxn],inv[maxn];
int a[maxn],b[maxn],len,ifac[maxn];
inline int ksm(int a,int b) {
int S=1;
while(b) {if(b&1) S=1ll*S*a%mod;b>>=1;a=1ll*a*a%mod;}
return S;
}
inline void NTT(int *f,int o) {
for(re int i=0;i<len;i++) if(i<rev[i]) std::swap(f[i],f[rev[i]]);
for(re int i=2;i<=len;i<<=1) {
int ln=i>>1,og1=ksm(G[o],(mod-1)/i);
for(re int l=0;l<len;l+=i) {
int t,og=1;
for(re int x=l;x<l+ln;++x) {
t=1ll*og*f[x+ln]%mod;
f[x+ln]=(f[x]-t+mod)%mod;
f[x]=(f[x]+t)%mod;
og=1ll*og*og1%mod;
}
}
}
if(!o) return;
int inv=ksm(len,mod-2);
for(re int i=0;i<len;i++) f[i]=1ll*f[i]*inv%mod;
}
int main() {
n=read(),k=read();fac[0]=1,inv[1]=1;ifac[0]=1;
for(re int i=2;i<=k;i++) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
for(re int i=1;i<=k;i++) fac[i]=1ll*fac[i-1]*i%mod;
for(re int i=1;i<=k;i++) ifac[i]=1ll*ifac[i-1]*inv[i]%mod;
len=1;while(len<=k+k+2) len<<=1;
for(re int i=0;i<len;i++) rev[i]=rev[i>>1]>>1|((i&1)?len>>1:0);
for(re int i=0;i<=k;i++)
a[i]=1ll*ifac[i]*ksm(i,k)%mod;
for(re int i=0;i<=k;i++)
if(i&1) b[i]=(mod-ifac[i])%mod;else b[i]=ifac[i];
NTT(a,0),NTT(b,0);
for(re int i=0;i<len;i++) a[i]=1ll*a[i]*b[i]%mod;
NTT(a,1);
int tot=n-1,now=1,ans=0;
for(re int i=1;i<=k;i++) {
now=1ll*now*tot%mod;
tot--;if(tot<0) break;
ans=(ans+1ll*a[i]*now%mod*ksm(2,n-1-i)%mod)%mod;
}
LL t=1ll*(n-1)*(n-2)/2;t%=(mod-1);
ans=1ll*ans*n%mod;
ans=1ll*ans*ksm(2,t)%mod;
printf("%d
",ans);
return 0;
}