题目描述

Given a integer n, you are asked to calculate the sum of the diameter of all unrooted labeled trees with n nodes labeled from 1 to n. Here the diameter of a tree is the length of the longest simple path on this tree, and the length of a path is the number of edges along this path.

Since the answer may be too large, you only need to output the result modulo a given prime number p.

输入格式

输出格式

Output a single integer, indicating the sum of the diameter of all labeled trees with nnn nodes modulo p.

样例

2 998244353

1

4 1000000007

44

6 1000000009

5322

提示

by 艾拉拉