Toàn mới nhận được \(𝑘\) phiếu giảm giá cho các cửa hàng bánh kẹo. Có \(𝑛\) loại kẹo được bày bán ở khu Toàn sống. Có \(2^n−1\) hãng cửa hàng khác nhau được đánh số từ \(1\) đến \(2^n−1\), và hãng thứ \(i\) có mở \(𝑎_i\) cửa hàng chi nhánh. Hãng thứ \(𝑖\) có bán loại kẹo \(𝑗 (1 ≤ 𝑗 ≤ 𝑛)\) nếu dạng biểu diễn nhị phân của \(𝑖\) có chứa bit thứ \(𝑗\). Toàn muốn mua được đủ một số loại kẹo Toàn thích, và dùng hết đúng \(𝑘\) phiếu giảm giá. Nhưng mỗi ngày, Toàn tùy hứng thay đổi sở thích ăn kẹo.

Cho \(𝑞\) truy vấn, truy vấn thứ \(𝑖\) là các loại kẹo mà Toàn muốn ăn vào ngày thứ \(𝑖\), giúp Toàn đếm xem có bao nhiêu cách chọn \(𝑘\) cửa hàng khác hãng đôi một với nhau, và có thể mua không thiếu các loại kẹo Toàn thích.

Kết quả lấy phần dư của số cách chia cho \(10^9+7\)

Tóm tắt: cho các số nguyên dương \(𝑎_1, 𝑎_2,..., 𝑎_{2^n-1} (𝑛 ≤ 20)\).

Cho \(𝑞 (𝑞 ≤ 10^5\)) truy vấn, mỗi truy vấn gồm một số nguyên \(𝑥 (0 ≤ 𝑥 < 2^n)\), tính tổng \(𝑎_{i_1}×𝑎_{i_2} ×...×𝑎_{i_k}\) của tất cả bộ số \(𝑖_1,..., 𝑖_k (𝑖_1 < 𝑖_2 < ...< 𝑖_k\)) sao cho (\(𝑖_1\) ∨ \(𝑖_2 \) ∨ ...∨\(𝑖_k)\)∧\(𝑥 = 𝑥\), với \(∨\) là phép \(OR\) và \(∧\) là phép \(AND.\)

Dữ liệu:

• Dòng thứ nhất chứa số \(𝑛, 𝑘 (𝑘 ≤ 3, 𝑛 ≤ 20)\)

• Dòng thứ hai chứa dãy số \(𝑎_1, 𝑎_2,..., 𝑎_{2^n-1} (0 ≤ 𝑎_i ≤ 10^9);\)

• Dòng thứ ba chứa \(𝑞 (𝑞 ≤ 10^5)\);

• Dòng thứ \(4...𝑞+3\): chứa một số nguyên \(𝑥 (0 ≤ 𝑥 < 2^n)\), nếu dạng biểu diễn nhị phân của \(𝑥\) có chứa bit \(𝑖\) thì hôm đó Toàn muốn ăn loại kẹo \(𝑖\).

Kết quả:

• Gồm \(𝑞\) dòng, mỗi dòng thứ \(𝑖\) là kết quả truy vấn thứ \(𝑖\).

Sample Input

2 2
1 2 3
1
1

Sample Output

11

Ràng buộc

• Subtask 1: \(𝑘 = 1,𝑛 ≤ 10 (5\)%\() \)

• Subtask 2: \(𝑘 = 1,𝑛 ≤ 17 (10\)%\() \)

• Subtask 3: \(𝑘 = 1,𝑛 ≤ 20 (25\)%\() \)

• Subtask 4: \(𝑘 = 2,𝑛 ≤ 20 (35\)%\() \)

• Subtask 5: \(𝑘 = 3,𝑛 ≤ 20 (25\)%\() \)