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

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

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

입력 형식

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

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

출력 형식

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

예제 입력 1

3
1 2 3
2
1
2

예제 출력 1

6
11

예제 입력 2

3
1 2 2
1
2

예제 출력 2

8

힌트

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

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

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