Background

CTT2021 D2T3.

Problem Description

Given a directed graph with $n$ vertices labeled $1,2,\dots,n$. Initially, for all $\forall i\in\{1,2,\dots,n-1\}$, there is a directed edge from $i$ to $i+1$.

You may add $m$ more directed edges (any start and end vertices are allowed). Multiple edges and self-loops are allowed.

Player A starts from vertex $1$ and moves as a random walk until reaching vertex $n$. You want to maximize the expected number of steps for Player A to move from $1$ to $n$.

A random walk is defined as follows: suppose Player A is currently at vertex $x$, and $x$ has $d$ outgoing edges. Then Player A chooses one of these $d$ outgoing edges uniformly at random and moves along it.

Input Format

The first line contains a positive integer $T$, the number of test cases. It is guaranteed that $T \le 10^5$.

The next $T$ lines each contain three integers $n,m,p$, representing the number of vertices in the directed graph, the number of edges you add, and the modulus for the answer. It is guaranteed that $1 \leq n \leq 10^9$, $0 \leq m \leq 10^{18}$, $2\leq p\leq 10^9+7$, and $p$ is a prime.

Output Format

Output $T$ lines. The $i$-th line contains an integer $ans$, meaning the maximum expected number of steps in the $i$-th test case modulo $p$.

(It can be proven that the answer is a rational number. Suppose its simplest form is $\frac{a}{b}$. Then you need to output an $ans$ such that $ans \cdot b \bmod p = a$. It is guaranteed that such an $ans$ exists.)

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

6
131
1206
161905971

Hint

Translated by ChatGPT 5