CF1679F.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 \lt 10^{n}$) such that for each $1 \le i \lt j \le k$ the number $x_i$ is not equivalent to the number $x_j$.

尤拉是一位数学家，他对世界的认知是如此绝对，仿佛他已经求解形式化问题长达百万万亿亿年。本题正是如此！

考虑区间 $[0, 10^{n})$ 内的所有非负整数。为方便起见，我们对所有数字在前面补零，使得该区间内的每个数恰好由 $n$ 位十进制数字组成。

给定一组数对 $(u_i, v_i)$，其中每个 $u_i$ 和 $v_i$ 均为 $0$ 到 $9$ 之间互不相同的十进制数字。

考虑一个由 $n$ 位数字组成的数 $x$。我们将从左到右依次对其各位数字编号，记为 $d_1, d_2, \ldots, d_n$。在一次操作中，当且仅当存在集合中的某个数对 $(u_j, v_j)$，使得以下任一条件成立时，才允许交换相邻的两位数字 $d_i$ 和 $d_{i + 1}$：

1. $d_i = u_j$ 且 $d_{i + 1} = v_j$，
2. $d_i = v_j$ 且 $d_{i + 1} = u_j$。

若可通过若干次上述操作将 $n$ 位数字组成的数 $x$ 变换为 $n$ 位数字组成的数 $y$，则称 $x$ 与 $y$ 等价。特别地，每个数均视为与自身等价。

给定整数 $n$ 和 $m$ 对数字 $(u_i, v_i)$ 组成的集合。你需要找出最大的整数 $k$，使得存在一组整数 $x_1, x_2, \ldots, x_k$（满足 $0 \le x_i \lt 10^{n}$），且对任意 $1 \le i \lt j \le k$，均有 $x_i$ 与 $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 \lt v_i \le 9$).

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

第一行包含一个整数 $n$（$1 \le n \le 50\,000$）—— 表示所考虑数字的位数。

第二行包含一个整数 $m$（$0 \le m \le 45$）—— 表示集合中数字对的个数。

接下来的 $m$ 行，每行包含两个数字 $u_i$ 和 $v_i$，以空格分隔（$0 \le u_i \lt v_i \le 9$）。

保证所有描述的数字对两两互不相同。

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 \lt 10^{n}$) such that for each $1 \le i \lt 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$.

输出一个整数——即最大的 $k$ 值，使得存在一组整数 $x_1, x_2, \ldots, x_k$（满足 $0 \le x_i < 10^{n}$），且对任意 $1 \le i < j \le k$，均有 $x_i$ 与 $x_j$ 不等价。

由于答案可能非常大，请输出 $k$ 对 $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$.

在第一个例子中，我们可以构造一个包含从 $0$ 到 $9$ 的所有整数的集合。显然，该集合中不存在两个等价的数。

在第二个例子中，存在唯一一对等价的数：$01$ 和 $10$。尽管数字 $1$ 存在，我们仍可构造一个包含从 $0$ 到 $99$ 的所有整数的集合。