graph

An undirected simple graph G can be divided into some connected components. Let x be the number of trees among these components, graph G's value is defined as x^k.

Given n and k, your task is to calculate the sum of values of all undirected simple graphs with exactly n vertices.

Print the answer module 998244353.

*Simple graph : A simple graph is an undirected graph in which both multiple edges and loops are disallowed.

*Connected component : In graph theory, a connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.

The first line contains an integer T <= 100, denoting the number of testcases.

T lines follow. Each line contains two space-seperated integers n <= 10000 and k <= 20.

For each testcase, print a single line containing the answer.

2
3 1
4 2

12
150

学军中学

2016 Multi-University Training Contest 8