配点 : $1100$ 点

問題文

先生が $(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} であるかを尋ね、先生が答えを教えます。 ただし、この質問への答えがそれ以前の答えから特定できる場合は、この質問を省略します。

このアルゴリズムで $\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}$

出力

答えを出力せよ。

2
1 2

2

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

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

4

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

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

0