{"problem":{"name":"Guessing Permutation for as Long as Possible","description":{"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. To do this, you prepared a sequence of pairs of integers $(A_1,B_1),(A_2,B_2),\\ldots,(A_","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc059_c"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nInput 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}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc059_c","tags":[],"sample_group":[["2\n1 2","2\n\nClearly, for any permutation $P$, you need to ask $1$ question."],["4\n1 2\n1 3\n2 3\n2 4\n3 4\n1 4","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."],["5\n1 2\n2 3\n3 4\n4 5\n1 5\n1 3\n2 4\n3 5\n1 4\n2 5","0"]],"created_at":"2026-03-03 11:01:14"}}