무시무시한 점화식

무시무시한 행렬은 첫 행과 첫 열이 직접 주어지고 나머지 원소는 간단한 점화식 하나로 정해지는 $n$차 정사각 행렬이다.

길이가 $n$인 정수 수열 $l$과 $t$, 그리고 정수 $a$, $b$, $c$가 주어질 때 무시무시한 행렬 $F$를 다음과 같이 정의한다.

• 첫 열은 수열 $l$이다: $F[k][1] = l_k$
• 첫 행은 수열 $t$이다: $F[1][k] = t_k$
• 나머지 원소는 $i, j \ge 2$에 대해 $F[i][j] = a \times F[i][j-1] + b \times F[i-1][j] + c$이다.

$F[n][n]$을 $10^6+3$으로 나눈 나머지를 구하라.

첫째 줄에 행렬의 크기 $n$과 점화식의 계수 $a$, $b$, $c$가 주어진다. ($2 \le n \le 200\,000$, $0 \le a, b, c \le 10^6$)

둘째 줄에 $l_1, \dots, l_n$이, 셋째 줄에 $t_1, \dots, t_n$이 주어진다. ($l_1 = t_1$, $0 \le l_k, t_k \le 10^6$)

$F[n][n]$을 $10^6+3$으로 나눈 나머지를 한 줄에 출력한다.