19468번 - Simple Graph 다국어

문제

An undirected simple graph $G$ can be divided into connected components. Let $x$ be the number of trees among these components. Then the value of graph $G$ 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$ labeled vertices. Print the answer modulo 998ドル,244円,353円$.

Note that a simple graph is an undirected graph in which both multiple edges and loops are disallowed. 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 not connected to any other vertex in the graph.

입력

The first line contains an integer $T \le 100,ドル denoting the number of test cases. Each of next $T$ lines contains two space-seperated integers $n$ and $k$ (1ドル \le n \le 10^4,ドル 1ドル \le k \le 20$).

출력

For each test case, print a single line containing the answer.

제한

힌트