13279번 - 곱의 합 쿼리

문제

N개의 수로 이루어진 수열 A가 주어진다. 이때, Q개의 쿼리를 실행한 결과를 구하는 프로그램을 작성하시오.

각각의 쿼리는 정수 K로 이루어져 있다. 수열 A의 부분 수열 중에서 크기가 K인 것을 모두 구한 다음, 각 부분 수열에 들어있는 수의 곱을 구한다. 그 다음 이 수의 합을 100003로 나눈 나머지를 출력한다.

수열 A의 크기가 K인 부분 수열의 개수는 _NC_K개이다.

입력

첫째 줄에 N(1 ≤ N ≤ 30000) 이 주어지고, 둘째 줄에는 수열에 포함되어 있는 수 A_i(1 ≤ A_i ≤ 100,000)가 주어진다.

셋째 줄에는 쿼리의 개수 Q(1 ≤ Q ≤ N)가 주어지고, 넷째 줄부터 Q개의 줄에는 각 쿼리에 해당하는 K(1 ≤ K ≤ N)가 주어진다.

출력

각각의 쿼리에 대해서 정답을 출력한다.

제한

힌트

예제 1의 경우에 K = 1이면 부분 배열은 {1}, {2}, {3}이 있다. 합은 1+2+3 = 6이다.

K = 2인 경우에 부분 배열은 {1, 2}, {2, 3}, {1, 3}있다. 합은 1*2 + 2*3 + 3*1 = 2+6+3 = 11이다.

예제 2의 경우에 K = 2이고, 부분 배열은 {1, 2}, {2, 2}, {1, 2}가 있다. 합은 1*2 + 2*2 + 2*1 = 2+4+2 = 8이다.