시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 1 | 1 | 1 | 100.000% |
Generating tests is always a boring and error-prone task for problem setters.
Recently, Rikka set a problem on trees, and now, she wants to generate some tests for this problem. At this time, Rikka tries an unusual way to generate trees. To generate a tree of size $n$:
Clearly, the result of this process must be a valid tree.
Now, Rikka wants to verify whether the generated tests are strong enough. For a tree $T$ of size $n$, she defines its complexity $c(T)$ as : $$c(T) = \sum_{i=1}^n \sum_{j=1}^n \text{dis}(T,i,j)$$ where $\text{dis}(T,i,j)$ is the number of edges in the path from vertex $i$ to vertex $j$ on tree $T$.
Rikka wants you to calculate the expectation of $c(T)$.
The first line contains two integers $n, p\ (1 \leq n \leq 3 \times 10^5, 10^8 \leq p \leq 10^9)$.
The input guarantees that $p$ is a prime number.
Output a single line with a single integer, the answer module $p$. Formally, if the simplest fraction representation of the answer is $\frac{x}{y}$, you need to output $x \times y^{p-2} \text{ mod } p$.
3 998244353
8
4 998244353
19
100 998244353
928958194
For the first sample, there is only one possible result, of which the complexity is equal to $8$.
For the second sample, there are two possible results, corresponding to the cases when the father of vertex $4$ is vertex $1$ or vertex $2$. The complexities of these two cases are $18$ and $20$ respectively.