给定一张 n 个点的有向图,点标号为 1,2,…,n,初始时对 ∀i∈{1,2,…,n−1},从 i 到 i+1 有一条有向边。
你可以在其中再加入 m 条有向边(起点终点任意),允许有重边和自环。
小 A 会从 1 出发,以随机游走的形式行动,直到抵达 n。你希望最大化小A从 1 移动到 n 的期望步数。
定义随机游走是这样的一种移动方式:设小 A 当前在点 x,x 有 d 条出边,则小 A 会从这 d 条出边中等概率随机选择一条走过去。
输入格式
从标准输入读入数据。
输入的第一行包含一个正整数 T,表示数据组数。
接下来 T 行,每行包含三个整数 n,m,p,分别表示有向图的点数、你添加的边数以及答案的模数。
输出格式
输出到标准输出。
输出 T 行,第 i 行一个整数 ans 表示第 i 组数据中最大的期望步数对 p 取模后的值(可以证明答案是有理数,设其用最简分数表示为 ab,则你需要满足 ans⋅bmod,保证这样的 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+7 且 p 是质数。