#P18416. Forever Young

Forever Young

Forever Young

小 Misha 喜欢玩由非负整数组成的无限长序列。如果一个序列单调不增,就称其为好序列。

每一步,Misha 可以把好序列中的某一个数增加或减少 11,但操作后仍必须是好序列。

最初 Misha 有序列 AA。他进行了恰好 kk 步操作,得到了序列 BB。求他一共可以用多少种不同的操作过程得到它。

输入格式

第一行一个整数 nn(0≤n≤600\le n\le60),表示 AA 中非零元素的个数。

第二行给出这 nn 个元素,满足 60≥a1≥a2≥⋯≥an>060\ge a_1\ge a_2\ge\cdots\ge a_n>0。AA 的其余元素都是零。n=0n=0 时这一行为空。

接下来两行以相同格式描述 BB。

此外保证 0≤∑ai≤600\le\sum a_i\le60,0≤∑bi≤600\le\sum b_i\le60。

最后一行一个整数 kk(0≤k≤1060\le k\le10^6)。

上述总和及非零项数限制针对初始、最终输入;操作中的序列仍须非负、单调不增,可以暂时超过初末的 60 格限制。

输出格式

输出不同操作过程的数量,对质数 998244353998244353 取模。

原样例

样例 1

3
3 2 1
3
3 2 1
2
7

样例 2

3
3 2 1
3
3 2 1
1111
0

说明

第一个样例中,全部七种方式如下,未写出的尾部元素均为零:

  1. {3,2,1}→{4,2,1}→{3,2,1}\{3,2,1\}\to\{4,2,1\}\to\{3,2,1\};
  2. {3,2,1}→{3,3,1}→{3,2,1}\{3,2,1\}\to\{3,3,1\}\to\{3,2,1\};
  3. {3,2,1}→{3,2,2}→{3,2,1}\{3,2,1\}\to\{3,2,2\}\to\{3,2,1\};
  4. {3,2,1}→{3,2,1,1}→{3,2,1}\{3,2,1\}\to\{3,2,1,1\}\to\{3,2,1\};
  5. {3,2,1}→{2,2,1}→{3,2,1}\{3,2,1\}\to\{2,2,1\}\to\{3,2,1\};
  6. {3,2,1}→{3,1,1}→{3,2,1}\{3,2,1\}\to\{3,1,1\}\to\{3,2,1\};
  7. {3,2,1}→{3,2}→{3,2,1}\{3,2,1\}\to\{3,2\}\to\{3,2,1\}。

第二个样例中,不可能恰好经过 1111 步从第一个序列变成第二个序列。