通过以下经典方式构造一棵树：

• 以顶点 1 为根。
• 对于每个从 2 到 $n$ 的顶点 $i$，依次从 $1$ 到 $i-1$ 中均匀随机选择一个顶点 $p$，并将 $p$ 作为 $i$ 的父节点。

设顶点 $u$ 的子树大小为 $s_u$，且 $f_u = s_u^k$（即 $s_u$ 的 $k$ 次幂）。对于每个顶点 $u$，计算 $f_u$ 的期望值，并对给定的质数 $M$ 取模。

形式化地，可以证明在以下约束条件下，每个期望值都可以表示为 $p/q$ 的形式，其中 $q$ 与 $M$ 互质。你需要输出所有顶点 $u$ 的期望值之和，对 $M$ 取模的结果。这里 $q^{-1}$ 是满足 $q \cdot q^{-1} \equiv 1 \pmod M$ 的整数。

输入格式

输入的第一行包含三个整数 $n, k$ 和 $M$ ($1 \le n \le 10^5$; $1 \le k \le 200$; $10^8 \le M \le 10^9+7$)。

保证 $M$ 是一个质数。

输出格式

输出一行，包含一个整数：所有顶点期望值之和对 $M$ 取模的结果。

样例

输入格式 1

3 1 1000000007

输出格式 1

3 500000005 1

输入格式 2

3 2 998244353

输出格式 2

9 499122179 1