题目描述

小 Misha 喜欢研究由非负整数组成的无限序列。若一个无限序列单调不增，则称它是好的。

在一步操作中，Misha 可以选择一个好的无限序列中的某一个数，将它增加 $1$ 或减少 $1$；但操作之后，整个无限序列仍然必须是好的。

最开始，Misha 手中有一个无限序列 $A$。他进行了恰好 $k$ 步操作后，得到了无限序列 $B$。请问他可能通过多少种不同的操作过程得到 $B$？

两个无限序列只会有有限个非零元素，未列出的其余元素都视为 $0$。

输入格式

第一行包含一个整数 $n$，表示序列 $A$ 中非零元素的个数。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示序列 $A$ 的非零元素。保证

其余所有元素均为 $0$。

接下来两行用相同格式描述序列 $B$：第一行给出非零元素个数，第二行给出这些非零元素。

此外，保证

最后一行包含一个整数 $k$。

输出格式

输出一个整数，表示可能的操作过程数量，对质数 $998244353$ 取模。

数据范围

• $0\le n\le 60$；
• $0\le k\le 10^6$；
• 序列 $A,B$ 的非零元素均为正整数，且均单调不增；
• 序列 $A,B$ 的所有非零元素均不超过 $60$；
• $\sum a_i\le 60$；
• $\sum b_i\le 60$。

样例 1

输入

3
3 2 1
3
3 2 1
2

输出

7

解释

七种方案分别为：

{3, 2, 1} -> {4, 2, 1} -> {3, 2, 1}
{3, 2, 1} -> {3, 3, 1} -> {3, 2, 1}
{3, 2, 1} -> {3, 2, 2} -> {3, 2, 1}
{3, 2, 1} -> {3, 2, 1, 1} -> {3, 2, 1}
{3, 2, 1} -> {2, 2, 1} -> {3, 2, 1}
{3, 2, 1} -> {3, 1, 1} -> {3, 2, 1}
{3, 2, 1} -> {3, 2} -> {3, 2, 1}

样例 2

输入

3
3 2 1
3
3 2 1
1111

输出

0

解释

无法在恰好 $1111$ 步后从第一个序列得到第二个序列。