{"problem":{"name":"Tree and Intervals","description":{"content":"You are given an integer $N$ and a prime $P$. For a tree with $N$ vertices labeled $1$ through $N$, let $a_i$ and $b_i$ be the endpoints of the $i$\\-th edge $(1 \\leq i \\leq N-1)$. Also, define $x_j\\ (","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4500,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc069_d"},"statements":[{"statement_type":"Markdown","content":"You are given an integer $N$ and a prime $P$.\nFor a tree with $N$ vertices labeled $1$ through $N$, let $a_i$ and $b_i$ be the endpoints of the $i$\\-th edge $(1 \\leq i \\leq N-1)$. Also, define $x_j\\ (1 \\leq j \\leq N-1)$ as:\n\n*   The number of integers $i\\ (1 \\leq i \\leq N-1)$ satisfying $\\min(a_i,b_i) \\leq j \\lt \\max(a_i,b_i)$.\n\nFind the number, modulo $P$, of sequences that could be $(x_1, x_2, \\ldots, x_{N - 1})$.\n\n## Constraints\n\n*   $2 \\leq N \\leq 500$\n*   $10^8 \\leq P \\leq 10^9$\n*   $P$ is prime.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $P$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc069_d","tags":[],"sample_group":[["3 998244353","3\n\nThere are three different trees with three vertices, if we distinguish the vertices by their labels but not the edges.  \nThe corresponding $(x_1, x_2)$ are $(1, 1)$, $(2, 1)$, and $(1, 2)$, so the expected output is $3$ modulo $P = 998244353$."],["69 433416647","243082757\n\nFind the count modulo $P$."]],"created_at":"2026-03-03 11:01:14"}}