#include #include #include #include using namespace std; // pow(a, b, m): a^b mod m(Pythonのpow(a, b, m)と同じ動作) long long modpow(long long a, long long b, long long m) { long long res = 1; a %= m; while (b > 0) { if (b & 1) res = res * a % m; a = a * a % m; b >>= 1; } return res; } int main() { int N, P, Q; cin >> N >> P >> Q; vector A(N); for (int i = 0; i < N; ++i) cin >> A[i]; sort(A.begin(), A.end()); int ans = 0; // 4つの組み合わせ全探索 for (int i = 0; i < N; ++i) { for (int j = i+1; j < N; ++j) { for (int k = j+1; k < N; ++k) { for (int l = k+1; l < N; ++l) { long long sum = modpow(10, A[i], P) + modpow(9, A[j], P) + modpow(7, A[k], P) + modpow(5, A[l], P); if (sum % P == Q) ans++; } } } } cout << ans << endl; return 0; }