AT_agc059_c.[AGC059C] Guessing Permutation for as Long as Possible

老师手中藏有一个 $ (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} $

输出答案。

限制

• $ 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) $ 不计入答案。

由 ChatGPT 4.1 翻译