소방관 (Firepersons)

소방관에게는 정수 등급이 부여되며, 이 등급은 다음과 같이 정의되는 정수 수열로 정해진다.

차수가 $k$인 수열은 처음 $k$개의 항 $a_0, a_1, \dots, a_{k-1}$과 정수 상수 $b_1, b_2, \dots, b_k$로 정의된다. $n \ge k$인 항은 다음 점화식으로 구한다.

$a_n = \left(\sum_{i=1}^{k} a_{n-i}\, b_i\right) \bmod 10000$

$i$번째로 오래된 소방관은 등급 $a_i$를 받는다. 수열의 매개변수와 정수 $i$가 주어질 때, $i$번째 소방관의 등급, 즉 이 수열의 제 $i$항 $a_i$를 구하여라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄에 다음 정수들이 공백 하나로 구분되어 순서대로 주어진다.

$k \quad a_0 \ \dots \ a_{k-1} \quad b_1 \ \dots \ b_k \quad i$

• $1 \le k \le 100$ : 수열의 차수
• $0 \le a_j < 10000$ : 수열의 처음 $k$개 항
• $0 \le b_j < 10000$ : 점화식의 곱셈 상수
• $0 \le i < 1\,000\,000\,000$ : 구하려는 항의 번호

입력의 끝은 $0$ 하나만 들어 있는 줄로 표시된다.

각 테스트 케이스마다 한 줄에 해당 수열의 제 $i$항 $a_i$를 출력한다. 출력하는 줄의 순서는 입력에 주어진 테스트 케이스의 순서와 같아야 한다.