Bộ số bằng nhau

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 Hiếu sử dụng lệnh này nhiều lần để tạo ra dãy $N$ số nguyên $a_1,a_2,\dots ,a_N$. Với $M$ giá trị bằng nhau: $a_{j_1},a_{j_2},\dots ,a_{j_M}$ ($1\le j_1<j_2<\dots <j_M\le N$), Hiếu 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}=\dots =a_{j_K}$, với $j_1<j_2<\dots <j_K$ sẽ tạo thành một bộ $K$.

Hai bộ được coi là khác nhau nếu tập chỉ số $\{j_1,j_2,\dots ,j_K\}$ của chúng khác nhau.

Yêu cầu: Với số nguyên dương $K$ cho trước, hãy giúp bạn Hiếu 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$ ($2\le N\le {10}^6$) và số nguyên dương $T$ là số lượng bộ test ($T\le 200$).
• Dòng 2: Ghi $N$ số nguyên $a_1,a_2,\dots ,a_N$ ($\left|a_i\right|\le {10}^6$, $1\le i\le N$).
• $T$ dòng tiếp theo, mỗi dòng ghi một số nguyên dương $K$ ($2\le K\le N$), cho biết cần tìm số lượng các bộ $K$ 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.

Dữ liệu ra

Ghi ra $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$.

Ràng buộc

• $2\le N\le {10}^6$, $1\le T\le 200$.
• $\left|a_i\right|\le {10}^6$.
• $2\le K\le N$.
• $20\%$ số test với $K\le N\le 20$; $T\le 10$; $0\le a_i\le {10}^6$;
• $40\%$ số test với $N\le 2·{10}^5$; $T=1$; $K=2$; $0\le a_i\le {10}^6$;
• $40\%$ số test với ràng buộc gốc.

Ví dụ