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.