题目描述

小可可又在造数据，只不过这次是一个联通图。

小可可要造一个 n 个点的联通图，由于她非常懒，于是决定每次在 [1, n] 中独立地等概率随机两个点 u, v（可以相同），然后将 u, v 之间连一条边。

小可可发现要等到整张图联通需要不少时间，于是问你期望连多少次边后整张图联通，答案对一个质数 p 取模。

输入格式

一行两个正整数 n, p，表示图的节点个数和模数。

输出格式

输出一个整数，表示期望连边次数对 p 取模的结果。

样例 1 输入

2 998244353

样例 1 输出

2

样例 2 输入

3 998244353

样例 2 输出

249561092

1 ≤ n ≤ 100, $10^8$ ≤ p ≤ $10^9$ + 9。