{"problem":{"name":"[北大集训 2021] 随机游走","description":{"content":"给定一张 $n$ 个点的有向图，点标号为 $1,2,\\dots,n$，初始时对 $\\forall i\\in\\{1,2,\\dots,n-1\\}$，从 $i$ 到 $i+1$ 有一条有向边。 你可以在其中再加入 $m$ 条有向边（起点终点任意），允许有重边和自环。 小 A 会从 $1$ 出发，以随机游走的形式行动，直到抵达 $n$。你希望最大化小 A 从 $1$ 移动到 $n$ 的期望步数。 定","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8989"},"statements":[{"statement_type":"Markdown","content":"给定一张 $n$ 个点的有向图，点标号为 $1,2,\\dots,n$，初始时对 $\\forall i\\in\\{1,2,\\dots,n-1\\}$，从 $i$ 到 $i+1$ 有一条有向边。\n\n你可以在其中再加入 $m$ 条有向边（起点终点任意），允许有重边和自环。\n\n小 A 会从 $1$ 出发，以随机游走的形式行动，直到抵达 $n$。你希望最大化小 A 从 $1$ 移动到 $n$ 的期望步数。\n\n定义随机游走是这样的一种移动方式：设小 A 当前在点 $x$，$x$ 有 $d$ 条出边，则小 A 会从这 $d$ 条出边中**等概率**随机选择一条走过去。\n\n## Input\n\n输入的第一行包含一个正整数 $T$，表示数据组数，保证 $T \\le 10^5$。\n\n接下来 $T$ 行，每行包含三个整数 $n,m,p$，分别表示有向图的点数、你添加的边数以及答案的模数，保证 $1 \\leq n \\leq 10^9$，$0 \\leq m \\leq 10^{18}$，$2\\leq p\\leq 10^9+7$ 且 $p$ 是质数。\n\n## Output\n\n输出 $T$ 行，第 $i$ 行一个整数 $ans$ 表示第 $i$ 组数据中最大的期望步数对 $p$ 取模后的值（可以证明答案是有理数，设其用最简分数表示为 $\\frac{a}{b}$，则你需要满足 $ans \\cdot b \\bmod p=a$，保证这样的 $ans$ 存在）。\n\n[samples]\n\n## Background\n\nCTT2021 D2T3\n\n## Note\n\n| 测试包编号 | $n\\le$ |  $m\\le$   | $T\\le$ | 特殊性质 | 分数 |\n| :--------: | :----: | :-------: | :----: | :------: | :--: |\n|    $1$     |  $5$   |    $5$    |  $10$  |    无    | $10$ |\n|    $2$     |  $5$   |  $10^2$   |  $10$  |    无    | $10 $ |\n|    $3$     | $10^8$ |  $10^2$   | $10^2$ |    无    | $20$ |\n|    $4$     |  $50$  |  $3,000$  |  $3$   |    无    | $20 $ |\n|    $5$     | $10^9$ |  $10^9$   | $10^5$ | $m<n-1$  | $10$ |\n|    $6$     | $10^9$ | $10^{18}$ | $10^5$ |    无    | $30$ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8989","tags":["2021","O2优化","CTT（清华集训/北大集训）"],"sample_group":[["4\n3 2 97\n10 25 233\n6 12345 2333\n1000000000 1000000000000000000 1000000007 \n","6\n131\n1206\n161905971\n"]],"created_at":"2026-03-03 11:09:25"}}