测试数据来自 system/2036

描述

Q先生是一个热爱学习的男孩子。

他知道任意正整数存在唯一的素数分解，在不忽略重数的情况下统计分解后得到的素数个数，就是这个整数的素因子个数。
例如 \(120=2^3 \times 3\times 5\)，所以 \(120\) 有 \(5\) 个素因子。

现在他给定了正整数 \(n\) 与另外一个正整数 \(p\)，希望你找到第 \(n\) 个（也就是第 \(n\) 小的）有至少 \(n\) 个素因子的整数，并输出其模 \(p\) 后的余数。

格式

输入格式

输入有一行，包含两个由空格隔开的正整数，分别为 \(n\) 和 \(p\)。

输出格式

输出一个正整数，表示第 \(n\) 个有至少 \(n\) 个素因子的整数模 \(p\) 后的余数。

样例1

样例输入1

5 123454321

样例输出1

80

样例说明1

前 \(6\) 个有不少于 \(5\) 个素因子的正整数依次为：\(32=2^5\), \(48=2^43\), \(64=2^6\), \(72=2^33^2\), \(80=2^45\) 和 \(96=2^53\)。

样例2

样例输入2

100 123454321

样例输出2

49932491

限制

对于 \(30\%\) 的数据，有 \(5\le n\le 500\)。

对于 \(60\%\) 的数据，有 \(5\le n\le 5000\)。

对于 \(100\%\) 的数据，有 \(5\le n\le 50000\) 且 \(10^8 \le p \le 2\times 10^8\)。

每一组数据时限为1秒。