QAQ的图论题

【题目描述】

QAQ喜欢玩无向简单图(简单图即图中无自环无重边)

定义函数$F(V,E)$表示一个图的价值，$F(V,E)=\sum\limits_{i=1}^{n}deg(i)^k$

也就是这个图的每个点的度数的$k$次方的和

为了方便计算，我们定义$0^0=1$

现在QAQ想要知道$n$个点的所有可能的无向简单的图的价值和是多少

由于答案可能很大，所以要求你对$998244353$取模后输出

【输入格式】

第一行输入$n，k$如题意所示

【输出格式】

输出相应的答案

【样例输入】

3 2

【样例输出】

36

【提示】

样例解释：

不难发现一共有$8$种情况，我们用一个三元组$(a,b,c)$表示$(1-2,2-3,3-1)$的边的状态

1、$(0,0,0)$ 价值为$0$

2、$(1,0,0)$ 价值为$1^2+1^2=2$

3、$(0,1,0)$ 价值为$1^2+1^2=2$

4、$(0,0,1)$ 价值为$1^2+1^2=2$

5、$(1,1,0)$ 价值为$1^2+2^2+1^2=6$

6、$(1,0,1)$ 价值同上也是$6$

7、$(0,1,1)$ 价值同上也是$6$

8、$(1,1,1)$ 价值为$2^2+2^2+2^2=12$

所以总和为$36$

对于10%的数据，$n<=5$

对于另外10%的数据，$k=0$

对于另外10%的数据，$k=1$

对于另外20%的数据，$n<=10^5$

对于另外20%的数据，$k<=10^3$

对于100%的数据，$n<=10^9,k<=10^5$