[AdditionalFile6715.zip](file://AdditionalFile6715.zip?type=additional_file)

#6715. 最大净商问题

标签: 传统 | 时间限制: 500 ms | 内存限制: 32 MiB |

题目描述

有 $N$ 个连续自然数 $x,x+1,x+2$ 一直到 $x+N-1$。已知 $N$，求那 $N$ 个数的乘积除以那 $N$ 个数的最小公倍数的商 $Q$ 的最大值。

数学课上，首先发现这个问题的公式的人把它叫做「最大净商问题」，其中的 $Q$ 就是「净商」。

---

求：

$$\max\left\{\frac{\prod_{i=x}^{x+N-1} i}{\mathrm{lcm}(x,x+1,\ldots ,x+N-1)}\right\}$$

输入格式

一行，包含两个数 $N$ 和 $P$。

输出格式

最大净商 $Q$ 模 $P$ 的值。

样例 1

输入

3 1000000007

输出

2

如果 $x = 4$，那么 $Q = \frac{120}{60} = 2$。没有更好的方法了，所以输出 $2$。

样例 2

输入

19 1000000007

输出

557316307

记得将答案模 $P$。

数据范围与提示

对于 $100\%$ 的数据，$1 \le N \le 10^6$，$P$ 为质数。