题号：NC213949
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
题目描述
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 :
%20%3D%20%5Csum_%7Bi%3D1%7D%5En%20%5Csum_%7Bj%3D1%7D%5En%20%5Ctext%7Bdis%7D(T%2Ci%2Cj))
where)
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).
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:
- Rikka sets vertex 1 as the root;
- For the i-th (i>1) vertex, let
be all factors of i where
. Rikka uniformly randoms an integer j from [1, k-1], and sets vertex
as the father of vertex i.
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 :
where
Rikka wants you to calculate the expectation of c(T).
输入描述:
The first line contains two integers.
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, you need to output
.
示例1
示例2