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 calculated using a frightful formula which is, actually, a simple recursive rule.
Given two integer sequences l and t, both of size n, as well as integer parameters a, b and c, the frightful matrix F is defined as follows:
The first column of the matrix is the sequence l: F[k,1]=lk.
The first row of the matrix is the sequence t: F[1,k]=tk.
Other elements are calculated using a recursive formula:
Given a frightful matrix, find the value of the element F[n,n] modulo 106+3.
The first line contains four integers n,a,b and c (2≤n≤200000,0≤a,b,c≤106) — the size of the matrix and the recursion parameters, as described in the problem statement.
The two following lines contain integers l1,...,ln and t1,...,tn, respectively (l1=t1,0≤lk,tk≤106).
Output a single integer — the value of F[n,n] modulo 106+3.