可怜的简单题

九条可怜今年出了一道简单题 —— 打算按照如下的方式生成一个随机的整数数列 A:

1 . 最开始，数列 A 为空。

2 . 可怜会从区间 [1,n] 中等概率随机一个整数 i 加入到数列 A 中。

3 . 如果不存在一个大于 1 的正整数 w，满足 A 中所有元素都是 w 的倍数，数组 A 将会作为随机生成的结果返回。否则，可怜将会返回第二步，继续增加 A 的长度。

现在，可怜告诉了你数列 n 的值，她希望你计算返回的数列 A 的期望长度。

时间限制：60000

内存限制：1048576

输入

输入一行两个整数 n, p (1 ≤ n ≤ 10¹¹, n < p ≤ 10¹²)，p 是一个质数。

输出

在一行中输出一个整数，表示答案对 p 取模的值。具体来说，假设答案的最简分数表示为 x/y，你需要输出最小的非负整数 z 满足 y × z ≡ x mod p。

样例输入

样例1：

2 998244353

样例2：

100000000 998244353

样例输出

样例1：

2

样例2：

3054970

这个问题涉及到概率和期望的计算，以及模运算。具体解答如下：

首先，我们需要理解题目的要求。题目要求我们计算一个随机生成的数列A的期望长度，该数列的生成规则是：从区间[1,n]中等概率随机选择一个整数加入到数列中，直到不存在一个大于1的正整数w，使得A中的所有元素都是w的倍数。

我们可以按照如下思路来求解：

1. 定义一个变量L，表示数列A的期望长度。
2. 对于每个数i（i从1到n），计算它以独立的方式被选入数列A的概率。由于每次选择是等概率的，所以每个数被选中的概率都是1/i。
3. 对于每个数i，我们需要计算它作为最后一个添加到数列A中的数的概率。这个概率等于i之前没有数满足是i的倍数的条件，即前i-1个数都不是i的倍数。这个概率可以通过连乘的方式计算，即(1 - 1/p) * (1 - 2/p) * … * (1 - (i-1)/p)。注意这里的p是一个质数。
4. 由于每个数被选中的概率是独立的，我们可以将每个数作为最后一个添加到数列A中的数的概率与它被选中的概率相乘，得到期望长度L的表达式。即L = Σ(i=1 to n) (1/i) * (连乘的结果)。注意这里的求和和连乘都需要对p取模。
5. 最后，我们需要计算这个表达式的值，并输出对p取模的结果。由于答案需要是最小的非负整数z满足y × z ≡ x mod p（其中x/y是答案的最简分数表示），我们可以使用扩展欧几里得算法来求解这个问题。

具体的C语言代码实现可能比较复杂，涉及到高精度运算和模运算。我们可以使用一些数学技巧来优化计算过程，比如使用递推关系来避免重复计算连乘的结果。此外，由于n和p的值可能非常大，我们需要使用高精度库来处理这些大数运算。在代码实现过程中，还需要注意处理一些特殊情况，比如当n较小时的边界情况。最后，我们需要仔细处理模运算的细节，确保计算结果的正确性。