QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 512 MB Total points: 100
[0]

# 3274. 随机游走

Statistics

给定一张 n 个点的有向图,点标号为 1,2,,n,初始时对 i{1,2,,n1},从 ii+1 有一条有向边。

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

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

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

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 T,表示数据组数。

接下来 T 行,每行包含三个整数 n,m,p,分别表示有向图的点数、你添加的边数以及答案的模数。

输出格式

输出到标准输出。

输出 T 行,第 i 行一个整数 ans 表示第 i 组数据中最大的期望步数对 p 取模后的值(可以证明答案是有理数,设其用最简分数表示为 ab,则你需要满足 ansbmod,保证这样的 ans 存在)。

样例数据

样例输入

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

样例输出

6
131
1206
161905971

数据范围与提示

测试包编号 n \le m \le T \le 特殊性质 分数
1 5 5 10 10
2 10^{2} 10
3 10^{8} 10^{2} 20
4 50 3000 3 20
5 10^{9} 10^{9} 10^{5} m\lt n-1 10
6 10^{18} 30

对于所有数据,保证 T \le 10^5,1 \leq n \leq 10^9,0 \leq m \leq 10^{18},2\leq p\leq 10^9+7p 是质数。