試しに、\(N = 3, P = 4\) として、前から順にとても良い列になるように \(A_i\) を決めることを考えます。
決めた部分までの総和を \(S\) とします。\(S\) が最後まで \(P\) の倍数にならなければ \(A\) はとても良い列です。

まず、\(A_1\) を決定します。\(A_1\) は \(1, 2, 3\) から選ぶことができます。
決定した後、\(S \bmod P = 1, 2, 3\) となる選び方の数はそれぞれ \(1, 1, 1\) です。

次に、\(A_2\) を決定します。\(A_2\) は \(S \bmod P = 1\) なら \(1, 2\) から、 \(S \bmod P = 2\) なら \(1, 3\) から、 \(S \bmod P = 3\) なら \(2, 3\) から選ぶことができます。
決定した後、\(S \bmod P = 1, 2, 3\) となる選び方の数はそれぞれ \(2, 2, 2\) です。

次に、\(A_3\) を決定します。\(A_3\) は \(S \bmod P = 1\) なら \(1, 2\) から、 \(S \bmod P = 2\) なら \(1, 3\) から、 \(S \bmod P = 3\) なら \(2, 3\) から選ぶことができます。
決定した後、\(S \bmod P = 1, 2, 3\) となる選び方の数はそれぞれ \(4, 4, 4\) です。

このように、\(N\) が \(1\) 増えるごとにとても良い列の数は \(2\) 倍になることがわかります。
これは、以下のように示すことができます。

• \(S \bmod P = 1, 2, \dots, P-1\) となる選び方の数がそれぞれ \(a, a, \dots, a\) であるとする。
• \(S \bmod P = 0\) となることを気にせず次の項を選ぶと、\(S \bmod P = 0, 1, 2, \dots, P-1\) となる選び方の数はそれぞれ \(a(P-1), a(P-2), a(P-2), \dots, a(P-2)\) である。
• \(S \bmod P = 0\) を除くと、\(S \bmod P = 1, 2, \dots, P-1\) となる選び方の数はそれぞれ \(a(P-2), a(P-2), \dots, a(P-2)\) である。

したがって、答えは \((P-1)(P-2)^{N-1}\) です。

回答例 (C++)

#include <iostream>
#include <atcoder/modint>
using namespace std;
using Modint = atcoder::modint1000000007;

int main(){
    int N, P;
    cin >> N >> P;
    Modint p = P;
    Modint ans = (p - 1) * (p - 2).pow(N - 1);
    cout << ans.val() << endl;
}

回答例 (Python)

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