You are given an array $\mbox{A}$ of size $N$. You are asked to answer $\mbox{Q}$ queries.

Each query contains a number $\mbox{M}$.

For each distinct permutation of the array $\mbox{A}$, you need to print the sum of the values returned by the find function.

As the sum can be too large, output it modulo $\mbox{P}$, which is a prime and given in input.

find(int permutation_A[], int M)
{
x = Length(permutation_A)
sum = 0
for(i = 0; i < x; i++) {
if (permutation_A[i] <= M)
sum = sum + permutation_A[i]
else
break
}
return sum
}

Input Format

The first line of input contains $\mbox{P}$.

The second line of input contains $N$. The next line contains $N$ numbers $A[0]\ldots A[N-1]$ separated by single spaces.

The next line contains $\mbox{Q}$, the number of queries to follow. Each subsequent line contains one positive integer $\mbox{M}$.

Output Format

For each query, output as asked above.

Constraints

$1000000\leq P\leq2000003$

$1\leq N\leq10^5$

$1\leq Q\leq10^5$

$1\leq A[i],M\leq10^9$

Sample Input

2000003
5
4 2 3 1 4
2
1
2

Sample Output

12
45

Explanation

Query 1:

Consider all permutations. if the first number is greater than 1, then the loop will break in the beginning itself. There are a total of 60 distinct permutations out of which 48 will give 0. The remaining 12 will fetch 1 each from the function. Thus the answer is 12.

见题面

见题面