#P8989. [北大集训 2021] 随机游走

[北大集训 2021] 随机游走

题目背景

CTT2021 D2T3

题目描述

给定一张 nn 个点的有向图,点标号为 1,2,,n1,2,\dots,n,初始时对 i{1,2,,n1}\forall i\in\{1,2,\dots,n-1\},从 iii+1i+1 有一条有向边。

你可以在其中再加入 mm 条有向边(起点终点任意),允许有重边和自环。

小 A 会从 11 出发,以随机游走的形式行动,直到抵达 nn。你希望最大化小 A 从 11 移动到 nn 的期望步数。

定义随机游走是这样的一种移动方式:设小 A 当前在点 xxxxdd 条出边,则小 A 会从这 dd 条出边中等概率随机选择一条走过去。

输入格式

输入的第一行包含一个正整数 TT,表示数据组数,保证 T105T \le 10^5

接下来 TT 行,每行包含三个整数 n,m,pn,m,p,分别表示有向图的点数、你添加的边数以及答案的模数,保证 1n1091 \leq n \leq 10^90m10180 \leq m \leq 10^{18}2p109+72\leq p\leq 10^9+7pp 是质数。

输出格式

输出 TT 行,第 ii 行一个整数 ansans 表示第 ii 组数据中最大的期望步数对 pp 取模后的值(可以证明答案是有理数,设其用最简分数表示为 ab\frac{a}{b},则你需要满足 ansbmodp=aans \cdot b \bmod p=a,保证这样的 ansans 存在)。

4
3 2 97
10 25 233
6 12345 2333
1000000000 1000000000000000000 1000000007 

6
131
1206
161905971

提示

测试包编号 nn\le mm\le TT\le 特殊性质 分数
11 55 55 1010 1010
22 10210^2 1010
33 10810^8 10210^2 2020
44 5050 3,0003,000 33 2020
55 10910^9 10910^9 10510^5 m<n1m<n-1 1010
66 101810^{18} 3030