## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## [Solution] Formalism for Formalism Codeforces Solution | Codeforces Problem Solution 2022

F. Formalism for Formalism
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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 $\left[0,{10}^{n}\right)$. 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 $\left({u}_{i},{v}_{i}\right)$, 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},\dots ,{d}_{n}$. In one operation you can swap digits ${d}_{i}$ and ${d}_{i+1}$ if and only if there is a pair $\left({u}_{j},{v}_{j}\right)$ 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 $\left({u}_{i},{v}_{i}\right)$. You have to find the maximum integer $k$ such that there exists a set of integers ${x}_{1},{x}_{2},\dots ,{x}_{k}$ ($0\le {x}_{i}<{10}^{n}$) such that for each $1\le i 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\phantom{\rule{thinmathspace}{0ex}}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

Print one integer — the maximum value $k$ such that there exists a set of integers ${x}_{1},{x}_{2},\dots ,{x}_{k}$ ($0\le {x}_{i}<{10}^{n}$) such that for each $1\le i 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\phantom{\rule{thinmathspace}{0ex}}244\phantom{\rule{thinmathspace}{0ex}}353$.