{"raw_statement":[{"iden":"background","content":"CTT2021 D2T3"},{"iden":"statement","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$ 条出边中**等概率**随机选择一条走过去。"},{"iden":"input","content":"输入的第一行包含一个正整数 $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"},{"iden":"output","content":"输出 $T$ 行，第 $i$ 行一个整数 $ans$ 表示第 $i$ 组数据中最大的期望步数对 $p$ 取模后的值（可以证明答案是有理数，设其用最简分数表示为 $\\frac{a}{b}$，则你需要满足 $ans \\cdot b \\bmod p=a$，保证这样的 $ans$ 存在）。"},{"iden":"note","content":"| 测试包编号 | $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$ |\n"}],"translated_statement":null,"sample_group":[["4\n3 2 97\n10 25 233\n6 12345 2333\n1000000000 1000000000000000000 1000000007 \n","6\n131\n1206\n161905971\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}