题目描述

老师手中藏有一个 $(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\leq a < b \leq N$）的整数对重新排列后的序列。接下来，你将从头开始依次检查这些对。对于每个对 $(A_i,B_i)$，你会询问 $P_{A_i} < P_{B_i}$ 是否成立，老师会告诉你答案。但如果这个问题的答案可以从之前所有问题的答案中唯一确定，则跳过该问题。

请你计算，有多少个排列 $P$，会使得按照上述算法，$\frac{N(N-1)}{2}$ 个问题全部都会被实际询问。将答案对 $10^9+7$ 取模后输出。

输入格式

输入从标准输入读入，格式如下：

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

输出格式

输出答案。

输入输出样例 #1

输入 #1

2
1 2

输出 #1

2

输入输出样例 #2

输入 #2

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

输出 #2

4

输入输出样例 #3

输入 #3

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

输出 #3

0

说明/提示

限制

• $2 \leq N \leq 400$
• $1 \leq A_i < B_i \leq N$
• $(A_i,B_i) \neq (A_j,B_j)$（$i \neq j$）
• 输入中的所有值均为整数。

样例解释 1

显然，对于任意排列 $P$，都需要询问一次问题。

样例解释 2

以 $P=(2,3,1,4)$ 为例。在前两次询问后，已知 $P_1 < P_2$ 且 $P_1 > P_3$，由此可以确定 $P_2 > P_3$，因此第三个问题可以被省略。因此，$P=(2,3,1,4)$ 不计入答案。