QQ扫一扫联系
可怜的简单题
九条可怜今年出了一道简单题 —— 打算按照如下的方式生成一个随机的整数数列 A:
1 . 最开始，数列 A 为空。
2 . 可怜会从区间 [1,n] 中等概率随机一个整数 i 加入到数列 A 中。
3 . 如果不存在一个大于 1 的正整数 w，满足 A 中所有元素都是 w 的倍数，数组 A 将会作为随机生成的结果返回。否则，可怜将会返回第二步，继续增加 A 的长度。
现在，可怜告诉了你数列 n 的值，她希望你计算返回的数列 A 的期望长度。
时间限制：60000
内存限制：1048576
输入
输入一行两个整数 n, p (1 ≤ n ≤ 1011, n < p ≤ 1012)，p 是一个质数。
输出
在一行中输出一个整数，表示答案对 p 取模的值。具体来说，假设答案的最简分数表示为 x/y，你需要输出最小的非负整数 z 满足 y × z ≡ x mod p。
样例输入
样例1：
2 998244353
样例2：
100000000 998244353
样例输出
样例1：
2
样例2：
3054970
