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.