20800번 - Rikka with Random Tree 다국어

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$:

1. Rikka sets vertex $1$ as the root;
2. For the $i$-th $(i>1)$ vertex, let $a_1, \dots, a_k$ be all factors of $i$ where $a_1=1,a_k = i$. Rikka uniformly randoms an integer $j$ from $[1, k-1]$, and sets vertex $a_j$ as the father of vertex $i$. 

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$.

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.