Counting Matrices with Given Row and Column Sums

You are given an n × 3 matrix consisting of non-negative integers. For this matrix, the sums of the elements in each row and for each of the 3 columns are provided. Count the number of matrices that satisfy these conditions.

More formally, let the matrix be denoted by x_ij (1 ≤ i ≤ n, 1 ≤ j ≤ 3) with x_ij ≥ 0. You are given the row sums r_i for 1 ≤ i ≤ n (i.e. r_i = x_i1 + x_i2 + x_i3) and the column sums c_j for 1 ≤ j ≤ 3 (i.e. c_j = ∑_i=1ⁿ x_ij). It is guaranteed that

\( \sum_{i=1}^{n} r_i = c_1 + c_2 + c_3 \).

Output the number of matrices that satisfy these conditions, modulo \(10^{17}\).

inputFormat

The input is given in the following format:

n
r1 r2 ... rn
c1 c2 c3

Here, n is the number of rows. The next line contains n non-negative integers representing the row sums. The last line contains 3 non-negative integers representing the column sums.

outputFormat

Output a single integer, the number of matrices that satisfy the given conditions, taken modulo \(10^{17}\).

sample

1
5
2 1 2

1