小 Misha 在玩由非负整数组成的无限数组。如果一个数组是单调不增的，我们称其为“好数组”。

在一步操作中，Misha 可以将好数组中的一个数字增加或减少 1，前提是操作后的数组仍然是好数组。

最初，Misha 有一个数组 $A$。Misha 进行了 $k$ 步操作，得到了数组 $B$。请问他有多少种不同的方式可以得到数组 $B$？

输入格式

第一行包含一个整数 $n$ ($0 \le n \le 60$)，表示 $A$ 中非零元素的个数。第二行包含 $n$ 个整数，用空格分隔：$60 \ge a_1 \ge a_2 \ge \dots \ge a_n > 0$，即这些元素本身。$A$ 的其余元素均为 0。

接下来的两行以相同的格式描述数组 $B$。

此外，保证 $0 \le \sum a_i \le 60$ 且 $0 \le \sum b_i \le 60$。

最后一行包含一个整数 $k$ ($0 \le k \le 10^6$)。

输出格式

输出方案数，对质数 $998\,244\,353$ 取模。

样例

输入 1

3
3 2 1
3
3 2 1
2

输出 1

7

输入 2

3
3 2 1
3
3 2 1
1111

输出 2

0

说明

在第一个样例中，方案如下： $\{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\}$。

在第二个样例中，无法在 $1111$ 步内从第一个数组得到第二个数组。