对于出题人来说，生成测试数据总是一项枯燥且容易出错的任务。

最近，Rikka 出了一道关于树的题目，现在她想要为这道题生成一些测试数据。这一次，Rikka 尝试用一种不同寻常的方法来生成树。生成一棵大小为 $n$ 的树的过程如下：

1. Rikka 将顶点 1 设为根节点；
2. 对于第 $i$ 个 ($i > 1$) 顶点，设 $a_1, \dots, a_k$ 为 $i$ 的所有因子，其中 $a_1 = 1, a_k = i$。Rikka 从 $[1, k - 1]$ 中均匀随机选择一个整数 $j$，并将顶点 $a_j$ 设为顶点 $i$ 的父亲。

显然，这个过程的结果必然是一棵合法的树。

现在，Rikka 想要验证生成的测试数据是否足够强。对于一棵大小为 $n$ 的树 $T$，她定义其复杂度 $c(T)$ 为：

$$c(T) = \sum_{i=1}^{n} \sum_{j=1}^{n} \text{dis}(T, i, j)$$

其中 $\text{dis}(T, i, j)$ 是树 $T$ 上从顶点 $i$ 到顶点 $j$ 的路径上的边数。

Rikka 希望你计算 $c(T)$ 的期望值。

输入格式

第一行包含两个整数 $n, p$ ($1 \le n \le 3 \times 10^5, 10^8 \le p \le 10^9$)。

输入保证 $p$ 是一个质数。

输出格式

输出一行一个整数，即答案对 $p$ 取模的结果。形式化地说，如果答案的最简分数表示为 $\frac{x}{y}$，你需要输出 $x \times y^{p-2} \pmod p$。

样例

样例输入 1

3 998244353

样例输出 1

8

样例输入 2

4 998244353

样例输出 2

19

样例输入 3

100 998244353

样例输出 3

928958194

说明

对于第一个样例，只有一种可能的结果，其复杂度等于 8。

对于第二个样例，有两种可能的结果，分别对应顶点 4 的父亲是顶点 1 或顶点 2 的情况。这两种情况的复杂度分别为 18 和 20。