Tý có \(N\) số nguyên dương \(A[1..N]\) (\(1 \le A[i] \le M, M = 2^K, K \le 20\)). Một tập con (khác rỗng) được gọi là "đặc biệt" nếu ước số chung lớn nhất (GCD) của các phần tử trong tập đúng bằng \(X\).

Hãy đếm số tập con khác rỗng có GCD đúng bằng \(X\), modulo \(10^9+7\).

Đầu vào:

• Dòng 1: \(N, K\) (\(N \le 10^5, K \le 20\))
• Dòng 2: \(N\) số nguyên \(A[1..N]\)
• Dòng 3: số \(X\) (\(1 \le X \le M\))

Đầu ra:

• Số tập con khác rỗng có GCD = \(X\), modulo \(10^9+7\).

#

Định dạng đầu vào

• Dòng 1: Số nguyên \(N\) (\(1 \le N \le 10^5\)).
• Dòng 2: \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^6\)).

Định dạng đầu ra

• In ra số lượng giá trị \(g\) khác nhau có thể là \(\gcd\) của một tập con khác rỗng.

Ví dụ

Input:

4
2 4 6 8

Output:

3

Giải thích: Các giá trị GCD có thể đạt được là {2, 4, 8}.

Ràng buộc & Subtasks