{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003esection pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n}\u003c/style\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\" class\u003d\"\"\u003e\n\t\t\t\u003cdiv class\u003d\"col-md-12\"\u003e\n\t\t\t\t\u003csection id\u003d\"description\" class\u003d\"problem-section\"\u003e\n\t\t\t\t\u003cdiv class\u003d\"headline\"\u003e\n\t\t\t\t\u003ch2\u003eDescription\u003c/h2\u003e\n\t\t\t\t\u003c/div\u003e\n\t\t\t\t\u003cdiv id\u003d\"problem_description\" class\u003d\"problem-text\"\u003e\n\t\t\t\t\u003cp\u003eGiven two integers $V$ and $E$, we say that an array $A$ of length $E$ is a valid \u003cem\u003econnectivity history array\u003c/em\u003e\u0026nbsp;(CHA, for short) if there exists a directed graph with $V$ vertices and $E$ edges and a permutation $P$ of length $E$ such that, if we were to start with an empty graph on $V$ vertices and add edges in the order given by permutation $P$, then it is true for all $1 \\le i \\le E$ that $A[i]$ is the number of strongly connected components in the graph after adding the $P[i]$-th edge.\u003c/p\u003e\r\n\r\n\u003cp\u003eFor example, for $V \u003d 3$ and $E \u003d 3$:\u003c/p\u003e\r\n\r\n\u003cp\u003e$A \u003d [3, 3, 3]$ is a valid CHA because there exists the graph $\\{(1, 2), (1, 3), (2, 3)\\}$. Regardless of the edge order chosen, the graph will always have three strongly connected components.\u003c/p\u003e\r\n\r\n\u003cp\u003e$A \u003d [3, 3, 1]$ is a valid CHA because there exists the graph $\\{(1, 2), (2, 3), (3, 1)\\}$. If we add the edges in exactly this order, the graph will have three strongly connected components after the first two edges, and a single strongly connected component after the third edge is added.\u003c/p\u003e\r\n\r\n\u003cp\u003e$A \u003d [3, 2, 1]$ is not a valid CHA because there does not exist a graph with three edges on three vertices and an order of adding edges such that the number of strongly connected components decreases after each added edge.\u003c/p\u003e\r\n\r\n\u003cp\u003eNote that the graph is not allowed to contain self-loops or multiple edges (but if the edge $(x, y)$ exists, the edge $(y, x)$ may also exist).\u003c/p\u003e\r\n\r\n\u003cp\u003eYou are given $Q$ queries, each consisting of a pair of integers $(V, \\mathit{MAX})$. Your task is to count the number of valid CHAs for each pair $(V, E)$ such that $1 \\le E \\le \\mathit{MAX}$.\u003c/p\u003e\r\n\n\t\t\t\t\u003c/div\u003e\n\t\t\t\t\u003c/section\u003e\n\t\t\t\u003c/div\u003e\n\t\t\t\t\t\t\t\t\t\t\u003cdiv class\u003d\"col-md-12\"\u003e\n\t\t\t\t\t\u003csection id\u003d\"input\" class\u003d\"problem-section\"\u003e\n\t\t\t\t\t\u003cdiv class\u003d\"headline\"\u003e\n\t\t\t\t\t\u003ch2\u003eInput\u003c/h2\u003e\n\t\t\t\t\t\u003c/div\u003e\n\t\t\t\t\t\u003cdiv id\u003d\"problem_input\" class\u003d\"problem-text\"\u003e\n\t\t\t\t\t\u003cp\u003eThe first line contains a single integer $Q$, the number of queries ($Q \\le 10$). In the next $Q$ lines, the $i$-th line describes the $i$-th query and contains three integers $V_i$, $\\mathit{MAX}_i$ and $\\mathit{MOD}_i$ ($1 \\le V_i \\le 50$, $1 \\le \\mathit{MAX}_i \\le V \\cdot (V - 1)$, $1 \\le \\mathit{MOD_i} \\le 10^9$).\u003c/p\u003e\r\n\n\t\t\t\t\t\u003c/div\u003e\n\t\t\t\t\t\u003c/section\u003e\n\t\t\t\t\u003c/div\u003e\n\t\n\t\t\t\t\u003cdiv class\u003d\"col-md-12\"\u003e\n\t\t\t\t\t\u003csection id\u003d\"output\" class\u003d\"problem-section\"\u003e\n\t\t\t\t\t\u003cdiv class\u003d\"headline\"\u003e\n\t\t\t\t\t\u003ch2\u003eOutput\u003c/h2\u003e\n\t\t\t\t\t\u003c/div\u003e\n\t\t\t\t\t\u003cdiv id\u003d\"problem_output\" class\u003d\"problem-text\"\u003e\n\t\t\t\t\t\u003cp\u003eOutput $Q$ lines, one line per query. The $i$-th line must contain $\\mathit{MAX}_i$ integers denoting the answers for the $i$-th query, taken modulo $\\mathit{MOD}_i$. The $j$-th integer on the $i$-th line must denote the number of valid CHAs for the pair $(V_i, j)$.\u003c/p\u003e\r\n\n\t\t\t\t\t\u003c/div\u003e\n\t\t\t\t\t\u003c/section\u003e\n\t\t\t\t\u003c/div\u003e\n\t\t\t\t\t\t\u003cdiv class\u003d\"col-md-12\"\u003e\n\t\t\t\u003csection id\u003d\"limit\" style\u003d\"display:none;\" class\u003d\"problem-section\"\u003e\n\t\t\t\u003cdiv class\u003d\"headline\"\u003e\n\t\t\t\u003ch2\u003eLimit\u003c/h2\u003e\n\t\t\t\u003c/div\u003e\n\t\t\t\u003cdiv id\u003d\"problem_limit\" class\u003d\"problem-text\"\u003e\n\t\t\t\t\t\t\u003c/div\u003e\n\t\t\t\u003c/section\u003e\n\t\t\t\u003c/div\u003e\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\u003cdiv class\u003d\"col-md-12\"\u003e\n\t\t\t\t\u003cdiv class\u003d\"row\"\u003e\n\t\t\t\t\t\u003cdiv\u003e\u003ch2\u003eSample 1\u003c/h2\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n5 10 666013\r\n6 9 10\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 2 4 9 21 50 110 209 351 546\r\n1 2 4 9 1 1 6 0 7\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\n\t\t\t\t\t\n\t\t\t\t\t\t\t\t\t\u003c/div\u003e\n\t\t\t\t\u003c/div\u003e\n\t\t\t\t\t\t\t\t\t\t\u003cdiv class\u003d\"col-md-12\"\u003e\n\t\t\t\t\u003csection id\u003d\"hint\" style\u003d\"display: none;\" class\u003d\"problem-section\"\u003e\n\t\t\t\t\u003cdiv class\u003d\"headline\"\u003e\n\t\t\t\t\u003ch2\u003eHints\u003c/h2\u003e\n\t\t\t\t\u003c/div\u003e\n\t\t\t\t\u003cdiv id\u003d\"problem_hint\" class\u003d\"problem-text\"\u003e\n\t\t\t\t\n\t\t\t\t\u003c/div\u003e\n\t\t\t\t\u003c/section\u003e\n\t\t\t\u003c/div\u003e\n\t\t\t\t\t\t\t\t\u003c/div\u003e"}}]}