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 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~.

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~.

Input

• Dòng 1: Ghi số nguyên dương ~N~ (~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~ (~|a_i| \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.

Output

• 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~.

Sample Input 1

6 2
4 5 4 6 6 4
2
4

Sample Output 1

4
0