← 返回题目列表

AtCoder · jsc2021_d

D. 无处P

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

分数: 400 点

问题陈述

给你一个素数 P 不小于 2,你不喜欢。

让我们调用一个整数数组 A_1, A_2, \dots, A_N 很好 如果满足以下条件:

  • 没有 i 与 1 \le i \le N 和 A_1 + A_2 + \dots + A_i \equiv 0 \bmod P.

考虑所有 (P-1)^N 长度数组 N 的元素来自 1 to P-1。其中有多少人 很好?

由于这个数字可能很大,所以输出它的模 (10^9 + 7).

约束

  • N 和 P 是整数。
  • 1 ≤ N ≤ 10^9
  • 2 ≤ P ≤ 10^9

输入

输入由标准输入按以下格式给出:

N P

输出

打印计数模数 (10^9 + 7).


示例输入 1

3 3

示例输出 1

2

两个数组, (1, 1, 2) 和 (2, 2, 1),满足条件。


示例输入 2

3 2

示例输出 2

0

示例输入 3

45108 2571593

示例输出 3

224219544