購入した商品の価格の積 \(P\) に対して得られるポイントは \(P\equiv 0\pmod M\) のとき \(0\) 、\(P{\;\not\equiv\;}0\pmod M\) のとき \(P ^ {-1}\) です。 \(M\) が素数であることから、これは \(P ^ {2M-3}\) を \(M\) で割った余りと等しいです。

\(P ^ {2M-3}\) は選んだ商品の \(A _ i\) に対する \({A _ i} ^ {2M-3}\) の積として求められることがわかります。 \({A _ i} ^ {2M-3}\) を \(M\) で割ったあまりをあらためて \(C _ i\) とおくと、次のような問題を解くことに帰着されます。

列 \(C=(C _ 1,C _ 2,\ldots,C _ N)\) が与えられる。列から重複しないよう \(K\) 個の要素を選び、それらの総積を選び方のスコアとする。このような選び方 \(_ N\mathrm C _ K\) 通りにわたるスコアの総和を \(M\) で割った余りを求めよ。

これは、多項式 \(1+C _ ix\) の総積の \(K\) 次の係数として求めることができます。

先頭から \(1+C _ ix\) をかけることで \(O(NK)\) 時間でこの問題を解くことができます。 次数の低い \(2\) つの多項式をかけることを繰り返すことで \(O(N(\log N) ^ 2)\) 時間とすることもできます（多項式の積を\({}\bmod M\) で高速に行う必要があります。AtCoder Library の畳み込みをそのまま用いることはできないので注意してください）。

実装例は以下のようになります。

#include <iostream>
#include <vector>
#include <atcoder/math>
using namespace std;

int main() {
    int N, K, M;
    cin >> N >> K >> M;
    vector<long> dp(K + 1); // K 次まで管理しておけばよい
    dp[0] = 1; // はじめは 1

    for (int i = 0; i < N; ++i) {
        int A;
        cin >> A;
        long C = atcoder::pow_mod(A, 2 * M - 3, M); // 商品のポイントへの寄与
        // 1 + Cx をかける
        for (int j = K; j > 0; --j) {
            (dp[j] += dp[j - 1] * C) %= M;
        }
    }
    cout << dp[K] << endl; // K 次の係数を出力
    return 0;
}

N, K, M = map(int, input().split())

dp = [0 for i in range(K + 1)] # K 次まで管理しておけばよい
dp[0] = 1 # はじめは 1

for A in map(int, input().split()):
    C = pow(A, 2 * M - 3, M) # 商品のポイントへの寄与
    # 1 + Cx をかける
    for j in range(K, 0, -1):
        dp[j] += dp[j - 1] * C
        dp[j] %= M

print(dp[K]) # K 次の係数を出力