Sum Gcd
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

给定一个 n 个正整数的序列 a，这 n 个数两两互质，给定一个正整数 k，求：

\sum_{i=1}^n\sum_{j=1}^n\frac{\gcd({a_i}\times{a_j},k)}{\gcd({a_i},k)}

特别地，答案对 2^{64} 取模。

输入描述:

第一行两个数 n,k(1\leq n\leq 10^6,1\leq k\leq 10^9) 。

第二行 n 个数，第 i 个数为 a_i(1\leq a_i\leq 10^9)。

输出描述:

一个数，表示答案。
示例1

输入

复制 
3 2
3 4 7

输出

复制 
11