Formalism for Formalism
Contest: Codeforces Round 791 (Div. 2)
Difficulty rating: 2600
Tags: bitmasks, dp, math

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$$$.

Input format:
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.

Output format:
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$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
1
0

Example output:
10

Example input:
2
1
0 1

Example output:
99

Editorial:
If you carefully read the problem statement, it becomes clear that we can do some transformations some numbers into others and we have to calculate the number of equivalence classes of all numbers consisting of $$$n$$$ digits. Let's say that the representative of some equivalence class is the lexicographically minimal number in this class. Now the problem is to calculate the number of distinct integers that are representatives of some equivalence classes.
For convenience let's build an undirected graph which vertices will be digits and an edge will connect some digits $$$u$$$ and $$$v$$$ if and only if we are given a pair of digits $$$(u, v)$$$ or a pair of digits $$$(v, u)$$$.
It's easy to see that the number is a representative of some class if and only if it doesn't have a substring of kind $$$[x, d_1, d_2, \ldots, d_s, y]$$$, where $$$x > y$$$, and there are edges $$$(y, d_s), (y, d_{s - 1}), \ldots, (y, d_1), (y, x)$$$ in the graph.
Now, knowing the criterium, let's calculate $$$dp[suff][mask]$$$ — the number of equivalence classes if we have added $$$suff$$$ digits from right to left in our number and now we can move to front only digits from the $$$mask$$$. Let's go over the next digit $$$c$$$ that will be added to the left. If there is a digit $$$i$$$ in the mask such that $$$c > i$$$ and there is an edge $$$(c, i)$$$ in the graph, we cannot add digit $$$c$$$, because it will break our criterium. Otherwise we can add digit $$$c$$$, it remains to calculate the new mask. Firstly, there will be a digit $$$c$$$ in the new mask. Secondly, all digits $$$i > c$$$ such that digit $$$i$$$ was in the old $$$mask$$$ and there is an edge $$$(c, i)$$$ in the graph, will be in the new mask too. After that let's perform a transition from state $$$(suff, mask)$$$ to state $$$(suff + 1, newMask)$$$.
The time complexity of this solution is $$$\mathcal{O}(n \cdot 2^\Sigma \cdot \Sigma^2)$$$, where $$$\Sigma$$$ is the size of the alphabet — $$$10$$$ for this problem.
It's slow a bit, so we will optimize this solution. We can precalculate the $$$newMask$$$ for each pair $$$(c, mask)$$$ using the algorithm described above. After that, using this information, we can recalculate $$$dp$$$ faster.
Time complexity: $$$\mathcal{O}(2^\Sigma \cdot \Sigma^2 + n \cdot 2^\Sigma \cdot \Sigma)$$$.