Product Sum Queries

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}$.

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$).

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

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$.