$1 \le a < b \le n$ を満たす $a,b$ の組 $(a,b)$ すべてからなる集合を考えます。これらすべての組の順列が平衡であるとは、$1 \le a < b < c \le n$ を満たす任意の $a,b,c$ について、その順列の中で組 $(a,c)$ が組 $(a,b)$ と組 $(b,c)$ の間にあることをいいます。すなわち、これら 3 つの組が、$(a,b),(a,c),(b,c)$ の順、または $(b,c),(a,c),(a,b)$ の順に現れます。

さらに、その順列には $m$ 個の追加の制約があり、$i$ 番目の制約は、組 $(a_i,b_i)$ が組 $(c_i,d_i)$ よりも前に現れなければならないことを表します。これら $m$ 個の制約を満たす平衡な順列の個数を求めてください。

入力

入力の最初の行には、空白で区切られた整数 $n,m$ が与えられます（$2 \le n \le 10$、$0 \le m \le 10$）。続く $m$ 行のうち $i$ 行目には、空白で区切られた整数 $a_i,b_i,c_i,d_i$ が与えられます（$1 \le a_i < b_i \le n$、$1 \le c_i < d_i \le n$、組 $(a_i,b_i)$ と組 $(c_i,d_i)$ は異なります）。

出力

すべての $i$ について $(a_i,b_i)$ が $(c_i,d_i)$ よりも前に現れる平衡な順列の個数を出力してください。この数は非常に大きくなる可能性があるので、素数 $998\,244\,353$ で割った余りを出力してください。

入出力例

入力 1

2 0

出力 1

1

入力 2

4 3
1 2 2 3
1 2 3 4
2 3 3 4

出力 2

2

注記

2 番目の例の順列は次のとおりです。

$(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)$；

$(1,2),(1,3),(2,3),(1,4),(2,4),(3,4)$。