Forever Young
小 Misha 喜欢玩由非负整数组成的无限长序列。如果一个序列单调不增,就称其为好序列。
每一步,Misha 可以把好序列中的某一个数增加或减少 1,但操作后仍必须是好序列。
最初 Misha 有序列 A。他进行了恰好 k 步操作,得到了序列 B。求他一共可以用多少种不同的操作过程得到它。
输入格式
第一行一个整数 n(0≤n≤60),表示 A 中非零元素的个数。
第二行给出这 n 个元素,满足 60≥a1≥a2≥⋯≥an>0。A 的其余元素都是零。n=0 时这一行为空。
接下来两行以相同格式描述 B。
此外保证 0≤∑ai≤60,0≤∑bi≤60。
最后一行一个整数 k(0≤k≤106)。
上述总和及非零项数限制针对初始、最终输入;操作中的序列仍须非负、单调不增,可以暂时超过初末的 60 格限制。
输出格式
输出不同操作过程的数量,对质数 998244353 取模。
原样例
样例 1
3
3 2 1
3
3 2 1
2
7
样例 2
3
3 2 1
3
3 2 1
1111
0
说明
第一个样例中,全部七种方式如下,未写出的尾部元素均为零:
- {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}。
第二个样例中,不可能恰好经过 1111 步从第一个序列变成第二个序列。