You are given an array of size . You are asked to answer queries.

Each query contains a number .

For each distinct permutation of the array , you need to print the sum of the values returned by the find function.

As the sum can be too large, output it modulo , 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 .
The second line of input contains . The next line contains numbers separated by single spaces.
The next line contains , the number of queries to follow. Each subsequent line contains one positive integer .

Output Format
For each query, output as asked above.

Constraints

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.