数数

【题目描述】

给定$n$个整数，输出这$n$个数中，$m$次幂能被$k$整除的数的个数。

【输入格式】

输入包含两行。

第一行是三个正整数$n,m,k$。

第二行是$n$个正整数。

【输出格式】

一行一个整数表示满足条件的数的个数。

【样例输入】

3 2 50
9 10 11

【样例输出】

1

【样例解释】

$9^2\mod 50=31$，$10^2\mod 50=0$，$11^2 \mod 50=21$，所以能整除的个数为1。

【数据范围与约定】

对于20%的数据，$n,m,k\leq 100$；

对于40%的数据,$n,m\leq 10^4,k\leq 1000$；

对于100%的数据，$n\leq 10^5,m\leq 10^6,k\leq 1000$，保证输入的$n$个正整数都不超过$10^8$。