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.

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.

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

Sample Input 1

3 3
1 2
1 3
2 3

Sample Output 1

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.

Sample Input 2

4 4
1 4
2 3
1 3
3 4

Sample Output 2

39

Sample Input 3

14 15
1 2
1 3
2 4
2 5
2 6
4 8
5 6
6 8
7 8
9 10
9 12
9 13
10 11
11 12
11 13

Sample Output 3

1613763

见题面 Input 部分

见题面 Output 部分