Frightful Matrix

A frightful matrix is a square matrix of order \( n \) where the first row and the first column are explicitly specified while the other elements are computed via a recursive formula.

You are given two integer sequences \( l \) and \( t \), each of size \( n \), along with three integer parameters \( a, b, \) and \( c \). The matrix \( F \) is defined as follows:

• \( F[k, 1] = l_k \) for \( k = 1,2,\dots,n \).
• \( F[1, k] = t_k \) for \( k = 1,2,\dots,n \).
• For \( i > 1 \) and \( j > 1 \), \( F[i,j] = a \cdot F[i,j-1] + b \cdot F[i-1,j] + c \).

The task is to compute \( F[n,n] \) modulo \( 10^6+3 \).

inputFormat

The first line contains an integer \( n \) representing the order of the matrix.

The second line contains \( n \) space-separated integers representing the sequence \( l \) (the first column of the matrix).

The third line contains \( n \) space-separated integers representing the sequence \( t \) (the first row of the matrix).

The fourth line contains three space-separated integers \( a, b, c \>.

outputFormat

Output a single integer: the value of \( F[n,n] \) modulo \( 10^6+3 \).

sample

2
1 2
1 3
1 1 1

6