Product Sum Queries

Time limit2sMemory limit512 MB

Summary

For each query K, sum the products of all K-element subsets of A, counting positions separately, modulo 100003.

Level: Medium6 of 10
Topics: Dynamic programming, Combinatorics, Math
Solved: No attempts yet

Problem

You are given a sequence $A$ of $N$ numbers. Write a program that answers $Q$ queries about it.

Each query is a single integer $K$ . Consider every way of choosing $K$ elements of $A$ , take the product of the $K$ chosen numbers for each way, add all of those products, and print the sum modulo $100003$ .

Choices are distinguished by position. Elements with equal values at different positions give different choices, so the number of ways is always the binomial coefficient $\binom{N}{K}$ .

Input

The first line contains $N$ ( $1 \le N \le 30000$ ).

The second line contains the elements $A_1, A_2, \dots, A_N$ ( $1 \le A_i \le 100000$ ), separated by spaces.

The third line contains the number of queries $Q$ ( $1 \le Q \le N$ ).

Each of the next $Q$ lines contains one $K$ ( $1 \le K \le N$ ).

Output

Print the answer to each query on its own line, in the order the queries are given.

Hint

For $A = (2, 3, 5)$ and $K = 2$ the choices are $\{2, 3\}$ , $\{2, 5\}$ , $\{3, 5\}$ . The products are $6$ , $10$ , $15$ and the sum is $31$ .

For $A = (4, 4, 7)$ and $K = 2$ there are still three choices, because the two $4$ s sit at different positions. The products are $16$ , $28$ , $28$ and the sum is $72$ .

Examples6

Example 1
Input
```
3
1 2 3
2
1
2
```
Expected output
```
6
11
```
Example 2
Input
```
3
1 2 2
1
2
```
Expected output
```
8
```
Example 3
Input
```
1
100000
1
1
```
Expected output
```
100000
```
Example 4
Input
```
5
2 3 5 7 11
1
5
```
Expected output
```
2310
```
Example 5
Input
```
4
5 5 5 5
4
1
2
3
4
```
Expected output
```
20
150
500
625
```

Example 6

Input

6
16380 42696 3700 39346 33246 70223
3
2
3
4

Expected output

32597
0
9826