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，一个K，3 <= N <= 2000，1<= 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]