Cho dãy \(a\) gồm \(n\) số nguyên và hai số nguyên \(k\), \(g\).

Yêu cầu: Hãy đếm số cách chọn \(k\) chỉ số \(1 \leq i_1 < i_2 < \ldots < i_k \leq n\) và \(\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 \leq k \leq n \leq 10^6, 1 \leq g \leq 10^6)\).
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) \((1 \leq a_i \leq 10^6)\).

Output

• Chứa một số nguyên 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