곱의 합 쿼리

길이가 $N$인 수열 $A$가 주어진다. 이 수열에 대한 쿼리 $Q$개를 처리하는 프로그램을 작성하시오.

각 쿼리는 정수 $K$ 하나로 이루어진다. 수열 $A$에서 원소를 $K$개 고르는 방법을 모두 살펴보고, 고른 $K$개의 곱을 각각 구한 다음, 그 곱을 전부 더한 값을 $100003$으로 나눈 나머지를 출력한다.

고르는 방법은 위치로 구분한다. 값이 같은 원소가 여러 개 있어도 위치가 다르면 서로 다른 방법이므로, 방법의 수는 항상 이항계수 $\binom{N}{K}$와 같다.

첫째 줄에 $N$ ($1 \le N \le 30000$)이 주어진다.

둘째 줄에 수열의 원소 $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 100000$)이 공백으로 구분되어 주어진다.

셋째 줄에 쿼리의 개수 $Q$ ($1 \le Q \le N$)가 주어진다.

넷째 줄부터 $Q$개의 줄에 각 쿼리의 $K$ ($1 \le K \le N$)가 한 줄에 하나씩 주어진다.

각 쿼리의 답을 입력에 주어진 순서대로 한 줄에 하나씩 출력한다.

$A = (2, 3, 5)$이고 $K = 2$이면 고르는 방법은 $\{2, 3\}$, $\{2, 5\}$, $\{3, 5\}$ 세 가지다. 곱은 각각 $6$, $10$, $15$이고 합은 $31$이다.

$A = (4, 4, 7)$이고 $K = 2$이면 두 $4$의 값이 같아도 위치가 다르므로 방법은 역시 세 가지다. 곱은 각각 $16$, $28$, $28$이고 합은 $72$이다.