第二回日本最強プログラマー学生選手権 D - Nowhere P【Python】

AtCoder ProblemsでDifficulty: 743、Solve Probability: 35%でした。

解けませんでした。
ユーザー解説

がわかりやすかったです。
先頭が1~1-Pで次の数字を考えるとたしかにそれまでの和がPの倍数になるものが1つあるようです。

MOD = 10 ** 9 + 7

N, P = map(int, input().split())
ans = (P - 1) * pow((P - 2), (N - 1), MOD)
print(ans % MOD)