算法分析
首先 $A_1$ 显然有 $P-1$ 种选择,对于之后的选法,由于 $A_1 + A_2 + \cdots A_i \not\equiv 0 \pmod P$,所以总是有一个数不能选,那么每个数就有 $P-2$ 种选择。
于是,最后的答案就是 $(P-1)\cdot (P-2)^{N-1}$
C++ 代码
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
using namespace std;
using mint = modint1000000007;
int main() {
int n, p;
cin >> n >> p;
mint ans = p-1;
ans *= mint(p-2).pow(n-1);
cout << ans.val() << '\n';
return 0;
}