Bạn được cho một dãy $a$ gồm $n$ phần tử và $q$ truy vấn. Mỗi truy vấn gồm một số nguyên $k$, hãy đếm số dãy con tăng của dãy $a$ có độ dài đúng bằng $k$.

Dãy con tăng độ dài k của dãy $a$ là một dãy con của $a$ thỏa mãn $a_{i_1}<a_{i_2}<a_{i_3}<...<a_{i_k}$ với $i_1<i_2<i_3<...<i_k$.

Input

Dòng đàu tiên chứa 2 số nguyên $n$ và $q$ ($n,q\le 500$).

Dòng thứ 2 chứa $n$ số tự nhiên, số thứ $i$ là $a_i$ ($a_i\le {10}^9$).

$q$ dòng tiếp theo, dòng thứ $j$ chứa một số nguyên $k_j$ ($k_j\le n$) thể hiện truy vấn thứ $j$.

Output

Gồm $q$ dòng, dòng thứ $j$ in ra một số nguyên duy nhất là số dãy con tăng có độ dài đúng bằng $k_j$, vì kết quả có thể rất lớn nên hãy lấy số dư khi chia cho ${10}^9+7$.

Sample Input

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

Sample Output

6
10
6
1

Subtasks

Subtask 1 (40%): $n,q\le 20$.

Subtask 2 (60%): Không có ràng buộc gì thêm.