题目描述

一位老师有一个隐藏的排列 $P=(P_1,P_2,\\ldots,P_N)$，其中 $P$ 是 $(1,2,\\cdots,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$，你需要问 $1$ 个问题。

样例输入 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