题目描述

先生が $(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$ で割った余りを求めてください。

输入格式

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

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

输出格式

答えを出力せよ。

题目大意

有一个 $1 \sim n$ 的排列 $P$。

给出 $\frac{n(n-1)}{2}$ 组互不相同的询问 $(A,B)\,(A \not= B)$，每次询问 $(A,B)$ 时，都能知道 $P_A,P_B$ 的大小关系。

已知对于任意的询问 $(A_i,B_i)$，在询问前都不知道 $P_{A_i},P_{B_i}$ 的大小关系，求可能的排列数量对 $10^9+7$ 取模的结果。

2
1 2

2

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

4

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

0

提示

制約

• $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$)
• 入力中のすべての値は整数である。

Sample Explanation 1

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

Sample Explanation 2

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