Trong lập trình, lệnh Random cho phép người lập trình tạo ra một giá trị ngẫu nhiên. Bạn Nam sử dụng lệnh này nhiều lần để tạo ra dãy \(N\) số nguyên \(a_1,a_2,…,a_N\). Với \(M\) giá trị bằng nhau: \(a_{j_1},a_{j_2},…,a_{j_M}\) \((1≤j_1<j_2<⋯j_M≤N)\), Nam nhận thấy chúng có thể tạo thành các bộ nhị (bộ hai phần tử bằng nhau), bộ tam (bộ ba phần tử bằng nhau), bộ tứ (bộ bốn phần tử bằng nhau), …, bộ \(K\) (bộ \(K\) phần tử bằng nhau).

Ví dụ:

\(a_{j_1}=a_{j_2}\), với \(j_1<j_2\) sẽ tạo thành một bộ nhị;

\(a_{j_1}=a_{j_2}=a_{j_3}\), với \(j_1<j_2<j_3\) sẽ tạo thành một bộ tam;

\(a_{j_1}=a_{j_2}=⋯=a_{j_K}\), với \(j_1<j_2<⋯<j_K\) sẽ tạo thành một bộ \(K\).

Yêu cầu:

• Với số nguyên dương \(K\) cho trước, hãy giúp bạn Nam xác định số lượng các bộ \(K\).

Dữ liệu vào:

• Dòng 1: Ghi số nguyên dương \(N (N≤10^6)\) và số nguyên dương \(T\) là số lượng bộ test \((T≤200)\);
• Dòng 2: Ghi \(N\) số nguyên \(a_1,a_2,…,a_N (|a_i |≤10^6,1≤i≤N);\)
• \(T\) dòng tiếp theo, mỗi dòng ghi một số nguyên dương \(K\) - cho biết cần tìm số lượng các bộ \(K (2≤K≤N)\) có thể tạo thành.

Các số trên một dòng cách nhau bởi một dấu cách.

Kết quả:

• Gồm \(T\) dòng tương ứng với \(T\) test, với mỗi test ghi kết quả là số lượng các bộ \(K\). Vì số lượng các bộ thoả mãn có thể rất lớn nên chỉ cần in ra phần dư cho \(10^9+7\).

Ví dụ:

Input

6 2
4 5 4 6 6 4
2
4

Output

4
0

Giải thích

• Các giá trị bằng nhau: \((a_1=a_3=a_6)\); \((a_4=a_5)\)
• Khi \(K = 2\), số lượng các bộ nhị là \(4:\) \((a_1,a_3 );(a_1,a_6 );(a_3,a_6 );(a_4,a_5)\)
• Khi \(K = 4\), số lượng các bộ tứ là \(0\).

Ràng buộc:

• 20% số test với \(K≤N≤20; T≤10; 0≤a_i≤10^6;\)
• 40% số test với \(N≤2.10^5; T=1; K=2; 0≤a_i≤10^6;\)
• 40% số test với ràng buộc gốc.