I. Interesting Graph
time limit per test
5 seconds
memory limit per test
256 mebibytes
input
standard input
output
standard output

You have an undirected graph with the following property:

For any subset $$$A$$$ of $$$7$$$ vertices of the graph, there are some two vertices $$$a, b \in A$$$ and some vertex $$$c \notin A$$$ such that all paths from $$$a$$$ to $$$b$$$ contain vertex $$$c$$$.

You need to find the number of ways to properly color this graph in $$$1, 2, \ldots, n$$$ colors modulo $$$998\,244\,353$$$.

A graph is colored in $$$k$$$ colors by assigning an integer color from $$$1$$$ to $$$k$$$ to every vertex. A coloring is proper if the endpoints of each edge in the graph have different colors.

Input

The first line of the input contains two integers $$$n$$$ and $$$m$$$: the number of vertices and the number of edges in your graph ($$$1 \leq n, m \leq 10^5$$$).

The next $$$m$$$ lines contain description of the edges of the graph. Each of these lines contains two integers $$$a_i$$$ and $$$b_i$$$ describing an edge between vertices $$$a_i$$$ and $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$, $$$a_i \neq b_i$$$). There are no multiple edges.

It is guaranteed that for any subset $$$A$$$ of $$$7$$$ vertices of the graph, there are some two vertices $$$a, b \in A$$$ and some vertex $$$c \notin A$$$ such that all paths from $$$a$$$ to $$$b$$$ contain vertex $$$c$$$.

Output

Print one line containing $$$n$$$ space-separated integers. The $$$i$$$-th integer must be the number of ways to properly color this graph in $$$i$$$ colors, taken modulo $$$998\,244\,353$$$.

Example
Input
5 3
3 5
5 1
1 3
Output
0 0 54 384 1500