28183번 - Forever Young 다국어

Little Misha plays with infinite arrays which consist of nonnegative integers. Let us call such an array good if it is non-increasing.

In one step, Misha can increase or decrease one number in a good array by $1$, if the array will remain good after this operation as well.

Initially, Misha had an array $A$. Misha made $k$ steps and obtained an array $B$. In how many ways he could have obtained it?

The first line contains a single integer $n$ ($0 \le n \le 60$): the number of nonzero elements in $A$. The second line contains $n$ integers separated by spaces: $60 \ge a_1 \ge a_2 \ge \cdots \ge a_n > 0$, the elements themselves. All other elements of $A$ are zeroes.

The next two lines contain a description of $B$ in the same format.

Additionally, it is guaranteed that $0 \le \sum a_i \le 60$ and $0 \le \sum b_i \le 60$.

The last line contains the only integer $k$ ($0 \le k \le 10^6$).

Print the desired number of ways modulo prime number $998\,244\,353$.

In the first sample, the ways are: $\{3,2,1\} \to \{4,2,1\} \to \{3,2,1\}$, $\{3,2,1\} \to \{3,3,1\} \to \{3,2,1\}$, $\{3,2,1\} \to \{3,2,2\} \to \{3,2,1\}$, $\{3,2,1\} \to \{3,2,1,1\} \to \{3,2,1\}$, $\{3,2,1\} \to \{2,2,1\} \to \{3,2,1\}$, $\{3,2,1\} \to \{3,1,1\} \to \{3,2,1\}$, $\{3,2,1\} \to \{3,2\} \to \{3,2,1\}$.

In the second sample, it is impossible to obtain the second array from the first in $1111$ steps.