#ifndef READ_MAIN #define READ_MAIN #include __FILE__ #pragma GCC optimize("Ofast") #pragma GCC target("avx2") const ll mod = 998244353; using mint = atcoder::modint998244353; //const ll mod = 1000000007; using mint = atcoder::modint1000000007; //------------------------------------------------------------------------------------------------------------------ //------------------------------------------------------------------------------------------------------------------ int main(){ fast(); int n, p, q; cin >> n >> p >> q; vector<int> A(n); rep(i, 0, n) cin >> A[i]; sort(all(A)); const int m = 2000009; vector<ll> calc5(m), calc7(m), calc9(m), calc10(m); rep(i, 0, n){ calc5[A[i]] = atcoder::pow_mod(5, A[i], p); calc7[A[i]] = atcoder::pow_mod(7, A[i], p); calc9[A[i]] = atcoder::pow_mod(9, A[i], p); calc10[A[i]] = atcoder::pow_mod(10, A[i], p); } int ans = 0; rep(a, 0, n) rep(b, a+1, n) rep(c, b+1, n) rep(d, c+1, n){ ll calc = calc5[A[d]] + calc7[A[c]] + calc9[A[b]] + calc10[A[a]]; calc %= p; if(calc == q) ans++; } cout << ans << newl; } #else #include <bits/stdc++.h> //// data structure //#include <atcoder/fenwicktree> //#include <atcoder/segtree> #include <atcoder/lazysegtree> //#include <atcoder/string> //// math #include <atcoder/math> //#include <atcoder/convolution> #include <atcoder/modint> //// graph //#include <atcoder/dsu> //#include <atcoder/maxflow> //#include <atcoder/mincostflow> //#include <atcoder/scc> //#include <atcoder/twosat> void fast(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout << std::setprecision(15); } /* バグが見つからないとき(RE)... 入力の仕方でミスっている可能性大 セグフォなら、配列の要素参照を、添字演算子から.at()に変えてみる 怪しい場所をコメントアウトしてコンパイルしてみる */ // g++ -ggdb -O2 hoge.cpp -I ~/.pml/ac-library -o zzz /* メイン関数内に記述すること std::ifstream in("testcase/hoge"); std::cin.rdbuf(in.rdbuf()); */ using ll = long long; using lll = __int128_t; using ld = long double; #define newl '\n' #define debug(x) cout << #x << " = " << (x) << newl; #define INF 1000390039 #define LLINF 1000000039000000039 #define IMAX INT_MAX #define IMIN INT_MIN #define LLMAX LONG_LONG_MAX #define LLMIN LONG_LONG_MIN #define shift(i) (1LL<<(i)) #define PI acos(-1) #define inr(l, x, r) (l <= x && x < r) #define fore(i, a) for(auto &i : a) #define rep(i, a, b) for(int i = (a); i < (b); i++) #define erep(i, a, b) for(int i = (a); i <= (b); i++) #define rrep(i, a, b) for(int i = (a); i >= (b); i--) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define pcnt(x) __builtin_popcount(x) #define llpcnt(x) __builtin_popcountll(x) #define vv(name, type, a, ...) vector<vector<type>> name(a, vector<type>(__VA_ARGS__)) #define vvv(name, type, a, b, ...) vector<vector<vector<type>>> name(a, vector<vector<type>>(b, vector<type>(__VA_ARGS__))) #define vvvv(name, type, a, b, c, ...) vector<vector<vector<vector<type>>>> name(a, vector<vector<vector<type>>>(b, vector<vector<type>>(c, vector<type>(__VA_ARGS__)))) #define vvvvv(name, type, a, b, c, d, ...) vector<vector<vector<vector<vector<type>>>>> name(a, vector<vector<vector<vector<type>>>>(b, vector<vector<vector<type>>>(c, vector<vector<type>>(d, vector<type>(__VA_ARGS__))))); template <typename T> int lwb(const std::vector<T>& vec, const T& x){ return lower_bound(all(vec), x) - vec.begin(); } template <typename T> int upb(const std::vector<T>& vec, const T& x){ return upper_bound(all(vec), x) - vec.begin(); } template <typename T> T max(const std::vector<T>& vec){ return *max_element(all(vec)); } template <typename T> T min(const std::vector<T>& vec){ return *min_element(all(vec)); } template <typename T> T rad(const T& x){ return x * PI/180; } template <typename T> using pq = std::priority_queue<T>; template <typename T> using pqg = std::priority_queue<T, std::vector<T>, std::greater<T>>; // @brief シフト演算子を、__int128_t型用にオーバーロード std::ostream& operator<<(std::ostream& os, __int128_t value){ if(value == 0) return os << 0; static char buffer[128]; if(value < 0){ os << '-'; value = -value; } int itr = 0; while(value > 0){ buffer[itr++] = value%10 + '0'; value /= 10; } std::reverse(buffer, buffer + itr); buffer[itr] = 0; return os << buffer; } // @brief string型の10進非負整数を、__128_t型に変換する __int128_t parse(const std::string& s){ __int128_t res = 0; for(int i = 0; i < s.length(); i++){ res = 10*res + (s[i]-'0'); } return res; } // 最大値・最小値の更新 template <typename T1, typename T2> bool chmax(T1 &a, const T2& b){ if(a < b){ a = b; return 1; } else return 0; } template <typename T1, typename T2> bool chmin(T1 &a, const T2& b){ if(a > b){ a = b; return 1; } else return 0; } template <typename T> void iota(std::vector<T>& vec, bool greater = false){ std::iota(all(vec), 0); std::sort(all(vec), [&](int i, int j){ if(greater) return vec[i] > vec[j]; return vec[i] < vec[j]; }); } // 2つのvectorをマージ template <typename T> std::vector<T> vmerge(std::vector<T>& a, std::vector<T>& b){ std::vector<T> res; std::sort(a.begin(), a.end()); std::sort(b.begin(), b.end()); std::merge(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(res)); return res; } // 辺 template <typename T> class Edge{ public: int from, to; T cost; int ID; Edge(int to, T cost) : to(to), cost(cost) {} // for WG Edge(int from, int to, T cost) : from(from), to(to), cost(cost) {} // for Edges Edge(int from, int to, T cost, int ID) : from(from), to(to), cost(cost), ID(ID) {} // for Edges bool operator<(const Edge<T>& rhs) const { return cost < rhs.cost; }; bool operator>=(const Edge<T>& rhs) const { return !(cost < rhs.cost); }; bool operator>(const Edge<T>& rhs) const { return cost > rhs.cost; }; bool operator<=(const Edge<T>& rhs) const { return !(cost > rhs.cost); }; bool operator==(const Edge<T>& rhs) const { return cost == rhs.cost; }; bool operator!=(const Edge<T>& rhs) const { return !(cost == rhs.cost); }; }; using G = std::vector<std::vector<int>>; template <typename T> using WG = std::vector<std::vector<Edge<T>>>; template <typename T> using Edges = std::vector<Edge<T>>; template <typename T, typename F> // @param ok 解が存在する値 // @param ng 解が存在しない値 // @remark ok > ng の場合は最小値、ok < ng の場合は最大値を返却 T Bsearch(T& ok, T& ng, const F& f){ while(std::abs(ok-ng) > 1){ T mid = (ok-ng)/2 + ng; (f(mid) ? ok : ng) = mid; } return ok; } template <typename T, typename F> T Bsearch_double(T& ok, T& ng, const F& f, int itr = 80){ while(itr--){ T mid = (ok+ng)/2; //T mid = sqrtl(ok*ng); (f(mid) ? ok : ng) = mid; } return ok; } template <typename T> // @brief (k, n-k)-shuffleである0, 1, ..., N-1 の置換Aを、辞書順で列挙する bool next_shuffle(std::vector<T>& vec, const int& k){ int n = vec.size(); if(n <= k){ return false; } // 前K項 := L // 後ろN-K項 := R auto left = vec.begin(); auto right = vec.begin() + k; T R_max = *std::max_element(right, vec.end()); T tmp = (std::numeric_limits<T>::min)(); // @param i Lの要素の中で、Rの要素の最大値よりも小さいもののうち、最大のもののイテレータ(*i := L_(i)) auto tmpi = left, i = right; while(tmpi != right){ if(tmp <= *tmpi && *tmpi < R_max){ tmp = *tmpi; i = tmpi; } tmpi++; } if(i == right){ return false; } // @param j Rの要素の中で、L_(i)よりも大きいもののうち、最小のもののイテレータ(*j := R_(j)) tmp = (std::numeric_limits<T>::max)(); auto tmpj = right, j = vec.end(); while(tmpj != vec.end()){ if(tmp >= *tmpj && *tmpj > *i){ tmp = *tmpj; j = tmpj; } tmpj++; } std::iter_swap(i, j); // L_(i)とR_(j)をswap i++, j++; // やりたいこと:L_(i+1)~L_(k-1)(:= X)とR_(j+1)~R_(n-k-1)(:= Y)を接続し、R_(j+1)が先頭に来るように回転する int X_len = k-std::distance(left, i); int Y_len = n-k-std::distance(right, j); int swap_len = std::min(X_len, Y_len); // Xの末尾swap_len項とYの末尾swap_len項をswapする std::swap_ranges(right-swap_len, right, j); if(swap_len == X_len){ std::rotate(j, j+swap_len, vec.end()); } else{ std::rotate(i, right-swap_len, right); } return true; } int log2ll(long long N){ int B = -1; while(N != 0){ B++; N /= 2; } return B; } template <typename T> // @brief (2,...,2)-shuffleである0, 1, ..., 2*N-1 の置換Aを、辞書順で列挙する bool next_pairing(std::vector<T>& vec){ int n = vec.size(); // @param used vecに含まれるどの数が使用済みであるか ll used = 0; for(int i = n-1; i >= 0; i--){ used |= (1<<vec[i]); if(i%2 == 1 && vec[i] < log2ll(used)){ // インクリメントできる vec[i] = __builtin_ctzll(used >> (vec[i]+1)) + vec[i]+1; used ^= (1<<vec[i]); for(int j = i+1; j < n; j++){ vec[j] = __builtin_ctzll(used); used ^= (1<<vec[j]); } return true; } } return false; } const int di4[4] = {-1, 0, 1, 0}; const int dj4[4] = {0, 1, 0, -1}; const int di8[8] = {-1, -1, 0, 1, 1, 1, 0, -1}; const int dj8[8] = {0, 1, 1, 1, 0, -1, -1, -1}; const std::vector<std::tuple<int, int, int>> line3{{0,1,2}, {3,4,5}, {6,7,8}, {0,3,6}, {1,4,7}, {2,5,8}, {0,4,8}, {2,4,6}}; const std::vector<std::tuple<int, int, int, int>> line4{{0,1,2,3}, {4,5,6,7}, {8,9,10,11}, {12,13,14,15}, {0,4,8,12}, {1,5,9,13}, {2,6,10,14}, {3,7,11,15}, {0,5,10,15}, {3,6,9,12}}; bool OutOfGrid(const int& i, const int& j, const int& h, const int& w){ if(i < 0 || j < 0 || i >= h || j >= w) return true; return false; } // @brief 繰り返し二乗法を利用した、x^nの求値 ll power(ll x, ll n){ ll res = 1; while(n){ if(n & 1) res *= x; x *= x; n >>= 1; } return res; } ll power_mod(ll x, ll n, const ll& m){ ll res = 1; while(n){ if(n & 1){ res = (res*x) % m; } x = (x*x) % m; n >>= 1; } return res; } // @brief x/mのfloor(x/m以下の最大の整数)を求める ll floor(const ll& x, const ll& m){ ll r = (x%m + m) % m; // xをmで割った余り return (x-r)/m; } // @brief x/mのceil(x/m以上の最小の整数)を求める ll ceil(const ll& x, const ll& m){ return floor(x+m-1, m); // x/m + (m-1)/m } // @brief prefix_sum[i][j] := [0, i)×[0, j) での二次元配列の総和 // @brief f(i, j) := a[i][j]の値 // @rem 貰う遷移で埋めていく template <typename T> std::vector<std::vector<T>> prefix_sum(const int& h, const int& w, const std::function<T(int, int)>& f) { std::vector<std::vector<T>> sum(h+1, std::vector<T>(w+1, T())); for(int i = 0; i < h; i++){ for(int j = 0; j < w; j++){ sum[i+1][j+1] = f(i, j) + sum[i][j+1] + sum[i+1][j] - sum[i][j]; } } return sum; } // @brief suffix_sum[i][j] := [0, i)×[0, j) での二次元配列の総和 // @brief f(i, j) := a[i][j]の値 // @rem 貰う遷移で埋めていく template <typename T> std::vector<std::vector<T>> suffix_sum(const int& h, const int& w, const std::function<T(int, int)>& f) { std::vector<std::vector<T>> sum(h+1, std::vector<T>(w+1, T())); for(int i = h-1; i >= 0; i--){ for(int j = w-1; j >= 0; j--){ sum[i][j] = f(i, j) + sum[i+1][j] + sum[i][j+1] - sum[i+1][j+1]; } } return sum; } using namespace std; #endif