점화식과 쿼리

수열 $\{x_n\}$은 모든 정수 $n \ge 2$에 대해 점화식 $x_n = ax_{n-1} + bx_{n-2} + n^k$를 만족한다. 첫 두 항 $x_0$, $x_1$과 점화식이 주어질 때 $x_n$을 출력하는 프로그램을 작성하시오.

첫째 줄에 정수 $x_0, x_1, a, b, k$가 공백으로 구분되어 주어진다. $(0 \le x_0, x_1, a, b, k \le 100\,000)$

둘째 줄에 정수 $Q$가 주어진다. $(1 \le Q \le 50\,000)$

셋째 줄부터 $Q$개의 줄에 정수 $n$이 한 줄에 하나씩 주어진다. $(0 \le n \le 10^{18})$

각 쿼리마다 $x_n$을 소수 $100\,003$으로 나눈 나머지를 한 줄에 하나씩 출력한다.

C/C++, Java 등의 언어에서 일부 변수를 32비트 정수형으로 선언하면 오버플로우가 발생할 수 있다.