配点 : 100 点
問題文
正整数 N 和素数 P 。 满足\displaystyle\prod_{k=1}^N k^k 该值应乘以 P 求余数。
制約
- 1 \leq N \leq 10^8
- 2 \leq P \leq 10^9+9
- P 是质数 如果正确答案是满足
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。
N P
部分点
- N \leq 10^6 的数据集,10 授予积分。
- 如果对于没有附加约束的数据集,除了上述之外,答案是正确的, 除以 90 授予积分。
出力
打印答案。
入力例 1
3 998244353
出力例 1
108
\displaystyle\prod_{k=1}^3 k^k=1 \times 4 \times 27=108 所以, 您最多只能移动到998244353 的余数为 108 。
入力例 2
1 1000000007
出力例 2
1
入力例 3
100 998244353
出力例 3
598189773