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:

$$$d_i = u_j$$$ and $$$d_{i + 1} = v_j$$$,
$$$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$$$.

Input

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.

Output

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

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

Formalism for Formalism

Examples