题目
问题描述
我们伟大的领袖 V 吃掉了树上的果实,得到了黑暗的力量,战无不胜。当 V 又一次获得了胜利的时候,他开始思考自己为什么会被赋予这样的天赋,决定拜访一些著名的哲学家寻找答案。
新日暮里一共有$n$个哲学家,任意两个哲学家之间都有可能有通讯,一个哲学家联盟指的是一个极大的哲学家集合,使得任意两名哲学家都可以直接或者间接地通讯。我们称新日暮里的哲学程度为哲学家联盟的个数的$m$次方, V 想知道对于通讯情况的哲学程度的和。
简化版题意:$n$个点的无向图,每条边都可能存在,一个图的权值是连通块个数的$m$次方,求所有可能的图的权值和。
答案对$998244353$取模。
输入格式
本题有多组数据,第一行一个整数$T$表示数据组数。
接下来$T$行每行两个正整数表示$n$和$m$。
输出格式
$T$行每行一个整数表示答案。
样例输入
4
2 2
3 1
5 3
100 13
样例输出
5
13
4818
33703375
数据范围与约定
对于$20\%$的数据$n \leq 7$
对于另外$20\%$的数据$n \leq 500$
对于另外$20\%$的数据$n \leq 2000$
对于$100\%$的数据$T \leq 1000, n \leq 30000,m \leq 15$
题解
(稍后再补)
代码
(稍后再补)