問題文

先生が $(1,2,\\cdots,N)$ の順列 $P=(P_1,P_2,\\ldots,P_N)$ を隠し持っています。 これから、あなたはこの順列を特定します。

そのために、あなたは整数のペアの列 $(A_1,B_1),(A_2,B_2),\\ldots,(A_{N(N-1)/2},B_{N(N-1)/2})$ を用意しました。これは、$(a,b)$ ($1 \\le a < b \\le N$) という形のすべてのペアを並べ替えたものです。 今から、あなたはこれらのペアを先頭から検査します。ペア $(A_i, B_i)$ に対しては、$P_{A_i}<P_{B_i}$ であるかを尋ね、先生が答えを教えます。 ただし、この質問への答えがそれ以前の答えから特定できる場合は、この質問を省略します。

このアルゴリズムで $\\frac{N(N-1)}{2}$ 個の質問がすべてされるような順列 $P$ の個数を $10^9+7$ で割った余りを求めてください。

制約

• $2 \\le N \\leq 400$
• $1 \\le A_i < B_i \\le N$
• $(A_i,B_i) \\neq (A_j,B_j)$ ($i \\neq j$)
• 入力中のすべての値は整数である。

入力

入力は標準入力から以下の形式で与えられる。

$N$ $A_1$ $B_1$ $A_2$ $B_2$ $\\vdots$ $A_{N(N-1)/2}$ $B_{N(N-1)/2}$

出力

答えを出力せよ。

入力例 1

2
1 2

出力例 1

2

明らかに、どの順列 $P$ に対しても、質問を一つする必要があります。

入力例 2

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

出力例 2

4

例として、$P=(2,3,1,4)$ を考えます。 この場合、二問目までで $P_1 < P_2$ と $P_1 > P_3$ を知って $P_2 > P_3$ と特定できるため、三問目を省略します。 従って、$P=(2,3,1,4)$ は数えません。

入力例 3

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

出力例 3

0