GCD 2

Cho một dãy \(n\) số nguyên \(a_1, a_2, \ldots, a_n\), cùng với hai số nguyên \(k\) và \(g\). Nhiệm vụ của bạn là đếm số cách chọn một tập hợp con gồm đúng \(k\) số từ dãy \(a\) sao cho ước chung lớn nhất (UCLN) của các số trong tập hợp đó bằng đúng \(g\).

Cụ thể hơn, bạn cần tìm số lượng các tập chỉ số \(1 \le i_1 < i_2 < \ldots < i_k \le n\) sao cho \(\gcd(a_{i_1}, a_{i_2}, \ldots, a_{i_k}) = g\).

Input

• Dòng đầu tiên chứa ba số nguyên \(n, k\) và \(g\) (\(1 \le k \le n \le 10^6\), \(1 \le g \le 10^6\)).
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^6\)).

Output

• In ra một số nguyên duy nhất là đáp án của bài toán, sau khi chia lấy dư cho \(10^9 + 7\).

Example

6 2 2
1 2 3 4 5 6

3