题目描述

有 $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

input

3 1000000007

output

2

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

样例 2

input

19 1000000007

output

557316307

记得将答案模 $P$。

数据范围与提示

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