Simple Graph

Time limit1sMemory limit512 MB

Summary

Sum x^k over all simple graphs on n labeled vertices, where x counts the tree components, modulo 998244353.

Level: Hard9 of 10
Topics: Combinatorics, Dynamic programming, Math, Graph
Solved: No attempts yet

Problem

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$ , calculate the sum of values of all undirected simple graphs with exactly $n$ labeled vertices. Print the answer modulo $998\,244\,353$ .

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.

Input

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

Output

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

Examples1

Example 1
Input
```
2
3 1
4 2
```
Expected output
```
12
150
```