#P18256. Ma Meilleure Ennemie
Ma Meilleure Ennemie
Ma Meilleure Ennemie
“我们能不能假装,这是第一次?”
Ekko 刚刚发明了能够回到过去的 Z-Drive。Heimerdinger 原本想用它把 Ekko 送回正确的宇宙,但异常现象造成了时空扭曲,使得 个 Ekko 来到了同一个宇宙。
现在共有 个宇宙,编号为 。Heimerdinger 使用以下方法决定把每个 Ekko 送到哪个宇宙:
- 将 Ekko 编号为 ,并划分成若干组。最初,所有 Ekko 都在同一组中。
- 选择一个尚未送走的组进行处理。
- 从 中选择一个好整数 。这里, 是好整数,当且仅当对当前组内的每个 Ekko ,编号为 的 Ekko 也在这一组中。
例如,当 、当前组为 时, 不是好整数,而 和 都是好整数。 - 把当前组划分成若干个临时组,使得每个临时组内的任意 Ekko 与 都属于同一个临时组。在所有满足条件的划分中,选择临时组数量最多的划分。
例如,当 、当前组为 、 时,会划分成 和 。 - 如果只得到一个临时组,就把该组所有 Ekko 送到宇宙 ;否则,这些临时组分别成为新的组,继续按照上述方法处理。
虽然这个方法可能把多个 Ekko 送往同一个宇宙,但现在已无暇修正。
给定 ,求这种方法能够产生多少种不同的最终结果。两种结果不同,当且仅当至少一名 Ekko 最终被送到的宇宙编号不同。
答案对 取模。
输入格式
输入一行两个整数 ,分别表示 Ekko 的数量和宇宙的数量。
输出格式
输出一行一个整数,表示不同最终结果的数量,对 取模。
数据范围
输入只有一组数据。分组时编号始终按最初的模 编号解释;各组可以分别选择不同的好整数。
样例 1
4 4
6
样例 2
2338 1470
18530141