#P8602. 湖人

    ID: 8689 传统题 1000ms 512MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>数论动态规划贪心CF2700筛法概率论模拟

湖人

Problem A. 湖人 (lakers.c/cpp/pas)

时间限制:1秒。内存限制:512MB。

呱正在玩一个游戏,现在黑板上写有 1,2,…,n1,2,\ldots,n 这 nn 个数,每一轮呱都会进行一个呱呱的操作,呱会从黑板上的数中等概率选取一个数xx,再将桌上xx 的倍数全部擦掉。呱一直重复呱呱的操作,直到黑板上所有的数都被擦掉,求呱期望进行多少次呱呱的操作才能结束游戏,请输出模pp意义下的结果。

Input

一行,nn 和pp。

Output

一行,答案。

Examples

样例输入

3 998245553

样例输出

2

Notes

• 对于 30% 的数据,n≤10n\le 10。

• 对于 60% 的数据,n≤106n\le 10^{6}。

• 对于 100% 的数据,1≤n≤1091\le n\le 10^{9},108<p≤109+710^{8}<p\le 10^{9}+7,并保证 pp 为质数。