<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

117. Counting

time limit per test: 0.25 sec.
memory limit per test: 4096 KB


Find amount of numbers for given sequence of integer numbers such that after raising them to the M-th power they will be divided by K.


Input

Input consists of two lines. There are three integer numbers N, M, K (0<N, M, K<10001) on the first line. There are N positive integer numbers − given sequence (each number is not more than 10001) − on the second line.


Output

Write answer for given task.


Sample Input

4 2 50
9 10 11 12
Sample Output

1
Author	: Michael R. Mirzayanov
Resource	: PhTL #1 Training Contests
Date	: Fall 2001

<|response|>
1. Abridged Problem Statement
   Given integers N, M, K and a list of N positive integers v₁…vₙ, count how many vᵢ satisfy
   (vᵢ)^M ≡ 0 (mod K).

2. Key Observations
   - Directly computing vᵢ^M by multiplying vᵢ M times and then taking mod K is O(M) per number, which in the worst case (M≈10⁴, N≈10⁴) can be about 10⁸ multiplications—too slow for a 0.25 s limit.
   - We only care about the result modulo K, and K≤10⁴.
   - We can use binary (fast) exponentiation under modulus to compute vᵢ^M mod K in O(log M) time.

3. Full Solution Approach
   1. Read integers N, M, K and the N values.
   2. Initialize a counter `answer = 0`.
   3. For each value v:
      a. Compute r = mod_pow(v, M, K), where mod_pow does exponentiation by squaring under modulus K in O(log M).
      b. If r == 0, increment `answer`.
   4. Print `answer`.

   Time Complexity: O(N · log M), which for N, M up to 10⁴ is roughly 10⁴ · 14 = 1.4·10⁵ modular multiplications—well within the time limit.

4. C++ Implementation
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, m, k;
vector<int> a;

void read() {
    cin >> n >> m >> k;
    a.resize(n);
    cin >> a;
}

int pw(int x, int p) {
    int r = 1 % k;
    while(p) {
        if(p & 1) {
            r = r * 1ll * x % k;
        }

        x = x * 1ll * x % k;
        p >>= 1;
    }

    return r;
}

void solve() {
    // A number v^M is divisible by K iff v^M mod K == 0, computed with fast
    // modular exponentiation. Count how many values in the sequence satisfy
    // this.

    int answer = 0;
    for(int v: a) {
        answer += pw(v, m) == 0;
    }

    cout << answer << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python Implementation with Detailed Comments
```python
import sys

def mod_pow(base, exp, mod):
    """
    Compute (base^exp) % mod using binary exponentiation.
    Runs in O(log exp) time.
    """
    result = 1 % mod       # handle mod == 1
    base %= mod            # reduce base immediately
    while exp > 0:
        if exp & 1:        # if lowest bit of exp is 1
            result = (result * base) % mod
        base = (base * base) % mod
        exp >>= 1          # shift exp right by 1 bit
    return result

def main():
    data = sys.stdin.read().split()
    N, M, K = map(int, data[:3])
    values = map(int, data[3:])

    answer = 0
    for v in values:
        # if v^M mod K == 0, count it
        if mod_pow(v, M, K) == 0:
            answer += 1

    print(answer)

if __name__ == "__main__":
    main()
```
