/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
2 以上の整数 P が与えられます。これはあなたの嫌いな数です。
整数の列 A_1, A_2, \dots, A_N が以下の条件を満たすとき、この列を とても良い 列と呼びます。
- 1 以上 N 以下のどの整数 i についても、A_1 + A_2 + \dots + A_i は P の倍数でない
各要素が 1 以上 P - 1 以下であるような長さ N の整数列は全部で (P - 1)^N 個存在しますが、このうち とても良い 列はいくつあるでしょうか？
ただし、答えは非常に大きくなることがあるので、答えを (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 つが条件を満たします。
入力例 2
3 2
出力例 2
0
入力例 3
45108 2571593
出力例 3
224219544
Score : 400 points
Problem Statement
You are given a prime number P not less than 2, which you don't like.
Let's call an array of integers A_1, A_2, \dots, A_N very good if it satisfies the following condition:
- there is no i with 1 \le i \le N and A_1 + A_2 + \dots + A_i \equiv 0 \bmod P.
Consider all (P-1)^N arrays of length N with elements from 1 to P-1. How many of them are very good?
As this number can be very big, output it modulo (10^9 + 7).
Constraints
- N and P are integers.
- 1 ≤ N ≤ 10^9
- 2 ≤ P ≤ 10^9
Input
Input is given from Standard Input in the following format:
N P
Output
Print the count modulo (10^9 + 7).
Sample Input 1
3 3
Sample Output 1
2
Two arrays, (1, 1, 2) and (2, 2, 1), satisfy the condition.
Sample Input 2
3 2
Sample Output 2
0
Sample Input 3
45108 2571593
Sample Output 3
224219544