无额外样例。

题目描述

小明正在画一棵二叉树。

第一笔，小明画了一个结点作为根结点。

接下来每一笔，小明会选择一个已画结点作为父结点，画出一条边及子结点。

当然，二叉树的左右儿子是有序的。并且，小明画的是二叉树，他保证不会画错。

小明定义一棵二叉树的“复杂度”为树上所有结点对之间的最短距离之和。所谓结点对之间的最短距离，指的是从一个结点到另一个结点所经过的边数。

问：画了 N 笔后，所画二叉树的“复杂度”的期望（记为 E）是多少？由于 E 可能是分数，你只需要输出 E · N! mod P 的值。其中 N! 表示 N 的阶乘。

输入格式

一行，包含两个整数 N, P

输出格式

一行，一个整数，表示答案

样例1输入

3 123456789

样例1输出

24

样例1解释

样例1，小明共画了 3 笔，有以下六种可能：

其中结点中的数字表示该结点是在第几笔画出来的。

不难发现，每一棵可能的二叉树的“复杂度”都是 4，则二叉树的“复杂度”的期望（平均“复杂度”）是 4*6/6 = 4.

4*3! mod 123456789 =24.

样例2输入

1234 998244353

样例2输出

371010878

数据范围