Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem F: Fuei的数论

Problem F: Fuei的数论

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 55  Solved: 5
[Submit][Status][Web Board]

Description

    Fuei被莫比乌斯反演血虐之后打算找几道简单的数论题练练手,没多久,他就发现了一道简单的数论题。给出N个数字,要你从中选出3个数字,ai,aj,ak,其中1 <= i < j < k <= N,要使得ai * aj * ak能被K整除,问你这样的选择有多少种。Fuei想了一会,发现他连这个也不会啊!!!所以他只能向聪明的你求助了。

Input

多个样例,请读到文件尾

输入一个N,一个K3 <= N <= 20001<= K <= 10^6

接下来N个数字,分别是a1,a2,a3,a4........aN,其中每个数字ai  1 <=ai<=10^8

Output

对于每组输入,输出一个数表示选择的方案数。

Sample Input

3 2
4 2 8

5 4  
4 5 7 10 8

3 2
3 5 7

Sample Output

1
9
0

HINT



注意数的溢出


[Submit][Status][Web Board]