{"raw_statement":[{"iden":"problem statement","content":"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.\nTo 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.\nFind 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$."},{"iden":"constraints","content":"*   $2 \\le N \\leq 400$\n*   $1 \\le A_i < B_i \\le N$\n*   $(A_i,B_i) \\neq (A_j,B_j)$ ($i \\neq j$)\n*   All values in the input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $B_1$\n$A_2$ $B_2$\n$\\vdots$\n$A_{N(N-1)/2}$ $B_{N(N-1)/2}$"},{"iden":"sample input 1","content":"2\n1 2"},{"iden":"sample output 1","content":"2\n\nClearly, for any permutation $P$, you need to ask $1$ question."},{"iden":"sample input 2","content":"4\n1 2\n1 3\n2 3\n2 4\n3 4\n1 4"},{"iden":"sample output 2","content":"4\n\nConsider $P=(2,3,1,4)$ as an example. In this case, you will skip the third question since you know $P_1 < P_2$ and $P_1 > P_3$ from previous questions and you can determine $P_2 > P_3$. Therefore, $P=(2,3,1,4)$ should not be counted."},{"iden":"sample input 3","content":"5\n1 2\n2 3\n3 4\n4 5\n1 5\n1 3\n2 4\n3 5\n1 4\n2 5"},{"iden":"sample output 3","content":"0"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}