살짝 정렬된 리스트

유르겐 군터스바르츠하펜슈트라센은 기타 연주 실력과 제자를 혹독하게 가르치는 방식으로 알려져 있다. 사람들이 잘 모르는 사실이 하나 더 있다. 그는 숫자도 좋아한다.

요즘 유르겐은 정렬된 리스트를 살펴보다가 싫증이 났다. 정렬된 리스트는 너무 뻔하고 개수도 적어서, 규칙을 조금 바꿔 보기로 했다.

양의 정수 $N$개로 이루어진 리스트 $\ell$이 있다. 원소가 서로 달라야 하는 것은 아니다. $\ell$에 나오는 모든 정수 $x > 1$에 대해 $\ell$에서 $x$가 마지막으로 나오는 자리보다 앞에 $x-1$이 한 번 이상 나오면, 유르겐은 이 리스트를 살짝 정렬된 리스트라고 부른다. 예를 들면 다음과 같다.

• $[2, 3, 1, 2]$는 살짝 정렬된 리스트다. 마지막 2보다 앞에 1이 있고, 마지막 3보다 앞에 2가 있다.
• $[2, 3, 4, 3, 2, 1, 3, 4]$는 살짝 정렬된 리스트가 아니다. 1이 모두 마지막 2보다 뒤에 있다.
• $[1, 1, 3, 1, 3, 3, 1, 3]$은 살짝 정렬된 리스트가 아니다. 마지막 3보다 앞에 2가 없다. 이 리스트에는 2가 아예 나오지 않는다.

유르겐은 원소가 모두 $K$ 이하의 양의 정수이고 길이가 $N$인 살짝 정렬된 리스트가 몇 개인지 알고 싶다. 두 리스트는 한 자리라도 원소가 다르면 서로 다른 리스트다. 유르겐 대신 그 개수를 세어 보자.

첫째 줄에 리스트의 길이 $N$과 질의의 개수 $Q$가 주어진다 ($1 \le N \le 5000$, $1 \le Q \le 1000$). 둘째 줄에 정수 $K_1, K_2, \dots, K_Q$가 주어진다. $i$번째 질의에서 세어야 하는 리스트는 $K_i$보다 큰 값을 포함하지 않는다 ($1 \le K_i \le 10^9$).

한 줄에 정수 $Q$개를 공백 하나로 구분해 출력한다. $i$번째 정수는 원소가 모두 $K_i$ 이하의 양의 정수이고 길이가 $N$인 살짝 정렬된 리스트의 개수다. 이 값이 매우 클 수 있으므로 $10^9+7$로 나눈 나머지를 출력한다.