<|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.  
   2. Initialize a counter `answer = 0`.  
   3. For each of the N values 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 with Detailed Comments  
```cpp
#include <bits/stdc++.h>
using namespace std;

// Compute (base^exp) % mod in O(log exp) time
int modPow(int base, int exp, int mod) {
    int result = 1 % mod;        // in case mod == 1
    base %= mod;                 // reduce base immediately
    while (exp > 0) {
        if (exp & 1) {
            // if the current bit of exp is 1, multiply result by base
            result = int((1LL * result * base) % mod);
        }
        // square the base for the next bit
        base = int((1LL * base * base) % mod);
        exp >>= 1;  // shift exp to process the next bit
    }
    return result;
}

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

    int N, M, K;
    cin >> N >> M >> K;

    int answer = 0;
    for (int i = 0; i < N; i++) {
        int v;
        cin >> v;
        // Compute v^M modulo K
        if (modPow(v, M, K) == 0) {
            answer++;
        }
    }

    cout << answer << "\n";
    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()
```