다항식과 쿼리 2

차수가 $N$이고 계수가 정수인 다항식 $f(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_N x^N$이 주어진다.

$K$개의 정수 $x_1, x_2, \ldots, x_K$가 주어졌을 때, $f(x_1), f(x_2), \ldots, f(x_K)$를 구하는 프로그램을 작성하시오.

첫째 줄에 다항식의 차수 $N$이 주어진다. ($0 \le N \le 250{,}000$)

둘째 줄에는 $N+1$개의 정수가 주어진다. $i$번째 정수는 다항식의 계수 $a_{i-1}$이다. ($0 \le a_i < 1{,}030{,}307$)

셋째 줄에는 정수의 개수 $K$가 주어진다. ($1 \le K \le 250{,}000$)

넷째 줄에는 $x_1, x_2, \ldots, x_K$가 주어진다. ($0 \le x_j < 1{,}030{,}307$)

총 $K$개의 줄을 출력한다. $i$번째 줄에는 $f(x_i)$를 $1{,}030{,}307$로 나눈 나머지를 출력한다.