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 đầu chứa số nguyên \(N\) và \(Q\) (\(N, Q \le 10^5\)).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả một cạnh.

Định dạng đầu ra

• In ra kết quả của từng truy vấn trên một dòng.

Ví dụ

Input:

5 3
1 2
1 3
2 4
2 5
2 3

Output:

3

Ràng buộc