Connectivity Value Sum over Spanning Subgraphs

Consider an undirected simple graph \(G\) with \(n\) vertices labeled \(1,2,\dots,n\) and \(m\) edges. A simple graph means there are no self-loops and no multiple edges. A spanning subgraph is obtained by removing zero or more edges from \(G\) (while keeping all \(n\) vertices). For any undirected graph, we define its connectivity value as the factorial of its number of connected components. In other words, if a graph has \(k\) connected components then its connectivity value is \(k!\) (i.e. \(k! = 1 \times 2 \times \cdots \times k\)).

Your task is to compute the sum of the connectivity values of all spanning subgraphs of \(G\), and output the result modulo \(998244353\) (i.e. \(998244353 = 7 \times 17 \times 2^{23}+1\), a prime number).

Note: Since there are \(2^m\) spanning subgraphs, you should design an algorithm that works under the given constraints. For this problem, it is guaranteed that \(1 \le n \le 20\) and \(0 \le m \le \frac{n(n-1)}{2}\).

inputFormat

The first line contains two integers \(n\) and \(m\): the number of vertices and edges, respectively. Each of the following \(m\) lines contains two integers \(u\) and \(v\) (\(1 \le u,v \le n\)) representing an edge between vertices \(u\) and \(v\).

outputFormat

Output a single integer: the sum of the connectivity values of all spanning subgraphs of \(G\) taken modulo \(998244353\).

sample

3 3
1 2
2 3
1 3

16