← 返回题目列表

AtCoder · pakencamp_2024_day3_2_l

L. k的k次方

中文机器翻译题面 查看原题

配点 : 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