점화식과 쿼리

수열 $ \{ x_n \} $이 정수 $n \ge 2$에 대해 점화식 $x_n = ax_{n-1} + bx_{n-2} + n^k $를 만족한다. 수열 $ \{ x_n \}$의 첫 두 항 $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$비트 정수형으로 선언한 경우 오버플로우가 발생할 수 있음에 유의하라.