测试数据来自 system/2386

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【题目描述】

　　给定正整数 \(n，m\)，然后有若干个整数 \(s\)，请判定 \(n^m\) 是否能被 \(s\) 整除。

【输入格式】

　　第一行为正整数 \(n，m\)，接下来的若干行，每行一个正整数 \(s\)。

【输出格式】

　　请输出能整除 \(n^m\) 的 \(s\) 的个数。

【输入输出样例】

　Input

2 3
1
2
3
4
5
6
7
8

　Output

4

【数据限制】

　　对于 \(100\%\) 的数据，\(2≤n≤10^9\)，\(2≤m≤300000\)，\(2≤s≤10^{18}\)，最多可能有100000个 \(s\)。

【来源】

　　Mr.he