题目描述

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:

• The first row of the matrix is the sequence t:

• Other elements are calculated using a recursive formula:

Given a frightful matrix, find the value of the element $F[n,n]$ modulo $10^6 +3$.

输入格式

The first line contains four integers n, a, b and c (2≤n≤200000, 0≤ a, b, c≤$10^6$) – 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 $10^6 +3$.

3 0 0 0 
0 0 2 
0 3 0

0

4 3 5 2 
7 1 4 3 
7 4 4 8

41817

提示

Central Europe Regional Contest 2015 Problem F