A15149. Formalism for Formalism

Yura is a mathematician, and his cognition of the world is so absolute as if he have been solving formal problems a hundred of trillions of billions of years. This problem is just that!

Consider all non-negative integers from the interval $[0, 10^{n})$ . For convenience we complement all numbers with leading zeros in such way that each number from the given interval consists of exactly $n$ decimal digits.

You are given a set of pairs $(u_i, v_i)$ , where $u_i$ and $v_i$ are distinct decimal digits from $0$ to $9$ .

Consider a number $x$ consisting of $n$ digits. We will enumerate all digits from left to right and denote them as $d_1, d_2, \ldots, d_n$ . In one operation you can swap digits $d_i$ and $d_{i + 1}$ if and only if there is a pair $(u_j, v_j)$ in the set such that at least one of the following conditions is satisfied:

1. $d_i = u_j$ and $d_{i + 1} = v_j$ ,
2. $d_i = v_j$ and $d_{i + 1} = u_j$ .

We will call the numbers $x$ and $y$ , consisting of $n$ digits, equivalent if the number $x$ can be transformed into the number $y$ using some number of operations described above. In particular, every number is considered equivalent to itself.

You are given an integer $n$ and a set of $m$ pairs of digits $(u_i, v_i)$ . You have to find the maximum integer $k$ such that there exists a set of integers $x_1, x_2, \ldots, x_k$ ( $0 \le x_i < 10^{n}$ ) such that for each $1 \le i < j \le k$ the number $x_i$ is not equivalent to the number $x_j$ .

The first line contains an integer $n$ ( $1 \le n \le 50\,000$ ) — the number of digits in considered numbers.

The second line contains an integer $m$ ( $0 \le m \le 45$ ) — the number of pairs of digits in the set.

Each of the following $m$ lines contains two digits $u_i$ and $v_i$ , separated with a space ( $0 \le u_i < v_i \le 9$ ).

It's guaranteed that all described pairs are pairwise distinct.

Print one integer — the maximum value $k$ such that there exists a set of integers $x_1, x_2, \ldots, x_k$ ( $0 \le x_i < 10^{n}$ ) such that for each $1 \le i < j \le k$ the number $x_i$ is not equivalent to the number $x_j$ .

As the answer can be big enough, print the number $k$ modulo $998\,244\,353$ .

In the first example we can construct a set that contains all integers from $0$ to $9$ . It's easy to see that there are no two equivalent numbers in the set.

In the second example there exists a unique pair of equivalent numbers: $01$ and $10$ . We can construct a set that contains all integers from $0$ to $99$ despite number $1$ .