For instance, let us assume \(N = 3, P = 4\) and determine \(A_i\) one by one from the first element so that it becomes very good.
Let \(S\) be the sum of the elements already determined. If \(S\) does not become a multiple of \(S\) all the time, then \(A\) is a very good sequence.

First, let us determine \(A_1\). We can choose \(A_1\) out of \(1, 2, 3\).
After choosing, the numbers of combinations such that \(S \bmod P = 1, 2, 3\) are \(1, 1, 1\), respectively.

Next, let us determine \(A_2\). If \(S \bmod P = 1\), \(A_2\) can be chosen from \(1\) or \(2\); if \(S \bmod P = 2\), it can be either \(1\) or \(3\); and if \(S \bmod P = 3\), it can be picked up from \(1\) or \(2\).
After choosing, the numbers of combinations such that \(S \bmod P = 1, 2, 3\) are \(2, 2, 2\), respectively.

Then, let us determine \(A_3\). If \(S \bmod P = 1\), \(A_3\) can be chosen from \(1\) or \(2\); if \(S \bmod P = 2\), it can be either \(1\) or \(3\); and if \(S \bmod P = 3\), it can be picked up from \(1\) or \(2\).
After choosing, the numbers of combinations such that \(S \bmod P = 1, 4, 3\) are \(4, 4, 4\), respectively.

As you can see, the numbers of very good sequences doubles every time \(N\) increases by one.
It can be shown as follows:

• Assume that the numbers of combinations of choices such that \(S \bmod P = 1, 2, \ldots, P-1\) are \(a, a, \dots, a\), respectively.
• If we determine the next term without minding becoming \(S \bmod P = 0\), the numbers of combinations such that \(S \bmod P = 0, 1, 2, \dots, P-1\) are a(P-1), a(P-2), a(P-2), \dots, a(P-2)$, respectively.
• By excluding \(S \bmod P = 0\), we can see that the numbers of combinations such that \(S \bmod P = 1, 2, \dots, P-1\) are \(a(P-2), a(P-2), \dots, a(P-2)\), respectively.

Therefore, the answer is \((P-1)(P-2)^{N-1}\).

Sample Code (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;
}

Sample Code (Python)

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