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

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

Print the answer as an integer.

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

13

Let w be the sequence of the mass of the weights, in ascending order of weight numbers.

• If w=(5,5,5), you obtain S= ===.
• If w=(2,2,3), you obtain S= =<<.
• If w=(6,8,6), you obtain S= <=>.
• If w=(9,4,4), you obtain S= >>=.
• If w=(7,7,3), you obtain S= =>>.
• If w=(8,1,8), you obtain S= >=<.
• If w=(5,8,8), you obtain S= <<=.
• If w=(1,2,3), you obtain S= <<<.
• If w=(4,9,5), you obtain S= <<>.
• If w=(5,1,8), you obtain S= ><<.
• If w=(6,9,2), you obtain S= <>>.
• If w=(7,1,3), you obtain S= >><.
• If w=(9,7,5), you obtain S= >>>.

While there is an infinite number of possible sequences of the mass of the weights, S is always one of the 13 above.