Problem Statement

A teacher has a hidden permutation $P=(P_1,P_2,\ldots,P_N)$ of $(1,2,\cdots,N)$. You are going to determine it.

To do this, you prepared a sequence of pairs of integers $(A_1,B_1),(A_2,B_2),\ldots,(A_{N(N-1)/2},B_{N(N-1)/2})$; this is a permutation of all pairs of the form $(a,b)$ ($1 \le a < b \le N$). Now, you will go over the pairs from the beginning. For a pair $(A_i, B_i)$, you will ask if $P_{A_i}<P_{B_i}$, and the teacher will tell you the answer. However, you will skip this question if you can already determine the answer to it from previous answers.

Find the number of permutations $P$, for which with your algorithm you will have to ask all $\frac{N(N-1)}{2}$ questions, modulo $10^9+7$.

Constraints

• $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$)
• All values in the input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.