@description@
“简单无向图”是指无重边、无自环的无向图（不一定连通）。
一个带标号的图的价值定义为每个点度数的k次方的和。
给定n和k，请计算所有n个点的带标号的简单无向图的价值之和。
因为答案很大，请对 998244353 取模输出。
input
第一行包含两个正整数n,k(1<=n<=10^9,1<=k<=200000)。
output
输出一行一个整数，即答案对 998244353 取模的结果。
sample input
6 5
sample output
67584000
@solution@
@part - 1@
考虑每一个点对答案的贡献，我们枚举这个点的度数为 i。
则总答案可以写成：
接下来就是对这个式子干一些奇怪的事情的时候了。
@part - 2@
在对式子干奇怪的事情之前，我们先来看个东西：
第二类斯特林数 (S(n, m))。定义为将 n 个数分成 m 个集合的方案数。
我们可以用它来求解一些经典组合（球盒）问题：
（1）将 n 个有区别的球放入 m 个无区别的盒子，不允许空盒，答案为 (S(n, m))。
（2）将 n 个有区别的球放入 m 个有区别的盒子，不允许空盒，答案为 (S(n, m)*m!)，就是上面那个排列一下。
（3）将 n 个有区别的球放入 m 个有区别的盒子，允许空盒。这个我们需要枚举有球的盒子数量，得到答案为 (sum_{i=0}^{m}C(m, i)*S(n, i)*i!)。
然后呢？注意，我们的第（3）个问题其实还有另外一种求解方法：每个球都有 m 个选择，乘法原理得到答案为 (m^n)。
也就是说，我们有这样一个等式成立：
这个等式几乎就包含了第二类斯特林数的所有了。
然后我们自然还关心怎么求解第二类斯特林数。有两种方法得到它的通项：
（1）使用容斥。用总方案 - 至少一个空盒 + 至少两个空盒 - ...。
（2）对上面那个等式使用二项式反演。
总之就能得到它的通项为：
然后把组合数拆成阶乘形式，整理一下：
是卷积没错了。固定 n 的情况下可以求出它的所有项。
@part - 3@
再回到我们乱搞的那个式子。显然 (n*2^{frac{(n-1)(n-2)}{2}}) 可以直接拿出去，我们相当于要乱搞 (sum_{i=0}^{n-1}C(n-1, i)*i^k)。
好。我们知道了这个过后，就可以把幂拆成斯特林数的形式了。比如我们要乱搞的那个式子拆 i^k：
现在把求和顺序改一下，将 j 提前。注意只有当 (j leq k) 时 (S(k, j)) 才会有值。
考虑后面那一个式子的组合意义：我们先从 n-1 个里面取出 i 个，再从 i 个里面选 j 个的方案数。
我们可以这样理解：先从 n-1 里面选 j 个，剩下的可选可不选的方案数。即：
这样子就够了吗？当然！不可能！注意 (n-1)! 我们是处理不出来的。我们先把组合数拆成阶乘形式，再约约分。
当 j 增加的时候，中间那个东西总是只会多一项。然后我们就可以搞了。
@accepted code@
#include<cstdio>
#include<algorithm>
using namespace std;
const int G = 3;
const int MAXK = 1000000;
const int MOD = 998244353;
int pow_mod(int b, int p) {
int ret = 1;
while( p ) {
if( p & 1 ) ret = 1LL*ret*b%MOD;
b = 1LL*b*b%MOD;
p >>= 1;
}
return ret;
}
int fct[MAXK + 5], inv[MAXK + 5];
void init() {
fct[0] = 1;
for(int i=1;i<=MAXK;i++)
fct[i] = 1LL*fct[i-1]*i%MOD;
inv[MAXK] = pow_mod(fct[MAXK], MOD-2);
for(int i=MAXK-1;i>=0;i--)
inv[i] = 1LL*inv[i+1]*(i+1)%MOD;
}
void ntt(int *A, int n, int type) {
for(int i=0,j=0;i<n;i++) {
if( i < j ) swap(A[i], A[j]);
for(int l=(n>>1);(j^=l)<l;l>>=1);
}
for(int s=2;s<=n;s<<=1)
for(int i=0,t=(s>>1),u=(type==1)?pow_mod(G,(MOD-1)/s):pow_mod(G,(MOD-1)-(MOD-1)/s);i<n;i+=s)
for(int j=0,p=1;j<t;j++,p=1LL*p*u%MOD) {
int x = A[i + j], y = 1LL*A[i + j + t]*p%MOD;
A[i + j] = (x + y)%MOD, A[i + j + t] = (x + MOD - y)%MOD;
}
if( type == -1 ) {
int ninv = 1LL*inv[n]*fct[n-1]%MOD;
for(int i=0;i<n;i++)
A[i] = 1LL*A[i]*ninv%MOD;
}
}
int g[MAXK + 5], h[MAXK + 5];
int main() {
int n, k, len, f; init();
scanf("%d%d", &n, &k); f = 1LL*n*pow_mod(2, 1LL*(n-1)*(n-2)/2%(MOD-1))%MOD;
for(int i=0;i<=k;i++)
g[i] = (MOD + 1LL*pow_mod(-1, i)*inv[i]%MOD)%MOD, h[i] = 1LL*pow_mod(i, k)*inv[i]%MOD;
for(len = 1;len <= 2*k;len <<= 1);
ntt(g, len, 1), ntt(h, len, 1);
for(int i=0;i<len;i++)
g[i] = 1LL*g[i]*h[i]%MOD;
ntt(g, len, -1);
int ans = 0, p = 1;
for(int i=0;i<=k&&i<n;i++) {
ans = (ans + 1LL*g[i]*p%MOD*pow_mod(2, n-i-1)%MOD)%MOD;
p = 1LL*p*(n-1-i)%MOD;
}
printf("%lld
", 1LL*ans*f%MOD);
}