Problem Statement

There are $N$ weights numbered $1,2, \dots,N$. Using a balance, we will compare weights $M$ times.

• Before the comparisons, prepare an empty string $S$.
• For the $i$-th comparison, put just weight $A_i$ to the left bowl, and just weight $B_i$ to the right.
• Then, one of the following three results is obtained.
• If weight $A_i$ is heavier than weight $B_i$,
  • append > to the tail of $S$.
  • If weight $A_i$ and weight $B_i$ have the same mass,
  • append = to the tail of $S$.
  • If weight $A_i$ is lighter than weight $B_i$,
  • append < to the tail of $S$.
• The result is always accurate.

After the experiment, you will obtain a string $S$ of length $M$. Among the $3^M$ strings of length $M$ consisting of >, =, and <, how many can be obtained as $S$ by the experiment? Since the answer can be enormous, print the answer modulo $998244353$.

Constraints

• All input values are integers.
• $2 \le N \le 17$
• $1 \le M \le \frac{N \times (N-1)}{2}$
• $1 \le A_i < B_i \le N$
• $i \neq j \Rightarrow (A_i,B_i) \neq (A_j,B_j)$

Input

The input is given from Standard Input in the following format:

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

Output

Print the answer as an integer.