Forever Young

Time limit2sMemory limit1024 MB

Summary

Count the ways to turn non-increasing array A into B in exactly k unit steps, where every intermediate array must also stay non-increasing.

Level: Hard9 of 10
Topics: Dynamic programming, Combinatorics, Math
Solved: No attempts yet

Problem

Little Misha plays with infinite arrays which consist of nonnegative integers. An array is called 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 remains good after this operation.

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

Input

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 describe $B$ in the same format.

It is guaranteed that $0 \le \sum a_i \le 60$ and $0 \le \sum b_i \le 60$ .

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

Output

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

Hint

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.

Examples2

Example 1
Input
```
3
3 2 1
3
3 2 1
2
```
Expected output
```
7
```
Example 2
Input
```
3
3 2 1
3
3 2 1
1111
```
Expected output
```
0
```