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   题解:先考虑单个点的贡献，枚举这个点与哪几个点相连，假设与i个点相连了之后，则包含这个情况的数量共有\[{2^{\frac{{(n - 1)*(n - 2)}}{2}}}\]种，即剩下n-1个点能生成多少个图 整理一下得:\[\sum\limits_{i = 1}^{n - 1} {C_{n{\rm{ - }}1}^i{i^k}{2^{\frac{{(n - 1)(n - 2)}}{2}}}} \] 主要考虑\[\sum\limits_{i = 1}^{n - 1} {C_{n{\rm{ - }}1}^i{i^k}} \]这个怎么算 有公式:\[{m^n} = \sum\limits_{i = 0}^m {C_m^i{\rm{\cdot}}S(n,i){\rm{\cdot}}i!} \] 把这个公式带进去得:\[\sum\limits_{i = 0}^{n - 1} {C_{n - 1}^i\sum\limits_{j = 0}^i {C_i^j \cdot S(k,j){\rm{j}}!} } \] 交换一下i,j的顺序:\[\sum\limits_{{\rm{j}} = 0}^{n - 1} {S(k,j){\rm{j}}!\sum\limits_{i = j}^{n - 1} {C_{n - 1}^iC_i^j} } \] 因为\[C_n^m \cdot C_{\rm{m}}^k = C_n^k{\rm{\cdot}}C_{n - k}^{m - k}\] 带进去得:\[\sum\limits_{j = 0}^{n - 1} {S(k,j){\rm{\cdot}}j! \cdot C_{n - 1}^j\sum\limits_{i = j}^{n - 1} {C_{n - 1 - j}^{i - j}}  = \sum\limits_{j = 0}^{n - 1} {S(k,j)}  \cdot \frac{{(n - 1)!}}{{(n - 1 - j)!}} \cdot } {2^{{\rm{n - }}1 - j}}\] \[S(k,j)\]可以用ntt处理出来，然后就可以直接计算了。