（提示，请先做完Easy Version，本题目相比于Easy Version，修改了模数，智子数量和组织数量，以及数据范围）

“你们是虫子。”

三体文明利用k个智子来监控k个组织&计划（如PDC，UN，面壁计划，太空军，舰队等）中的重要人物，第i个智子监控第i个组织的重要人物

第i个组织中，有$a_i$个重要人物

k个智子会生成各自的监控名单。 每个智子监控的人数没有单独限制， 但是，由于某些原因，三体方面只能同时接收p个监控信息，也就是说，这k个智子最多一共只能监控p个人

k份名单合在一起，就是一个监控计划。

三体人想知道，监控计划一共有多少种？ 两个监控计划不同，当且仅当存在一个智子监控的名单在两个计划中不相同。

一个智子的两份监控名单不相同，当且仅当存在某个重要人物（来自这个智子所应当监控的组织）出现在一个名单上，而在另外一个名单上没有出现。（可以参考样例解释）

显然，各个名单上的人数总和不能超过p，并且各个名单人数总和不能为空（这没有意义）（每一个智子监控的名单可以为空，但总的不能为空）

作为ETO一员的你，这是一个提升在主眼中地位的好机会。所以你主动请缨要来解决这个问题。

答案可能很大，你只需要告诉主，这个问题的答案对998244353取模的结果。

第一行一个正整数$k$$(1<=k<=10^5)$，表示有$k$个智子来监控$k$个组织
第二行$k$个正整数，数之间用空格分开，表示$a_1,a_2,...,a_k$，即每个组织中的重要人物数目

$1<=a_1<=10^6$ 且$\sum_{i=1}^k a_i <= 10^6$，即$a_i$之和小于等于$10^6$

第三行一个正整数$p$，表示$k$个智子最多一共监视$p$个人,$1<=p<=\sum_{i=1}^k a_i$

输出一行一个数，表示答案对998244353取模的结果

设这五个人为a1,a2,b1,c1,c2
三份名单为A,B,C
则方案分别为：
$A=\emptyset,B={b1},C=\emptyset$
$A=\emptyset,B=\emptyset,C={c1}$
$A=\emptyset,B=\emptyset,C={c2}$
$A=\emptyset,B={b1},C={c1}$
$A=\emptyset,B={b1},C={c2}$
$A=\emptyset,B=\emptyset,C={c1,c2}$
$A={a1},B=\emptyset,C=\emptyset$
$A={a1},B={b1},C=\emptyset$
$A={a1},B=\emptyset,C={c1}$
$A={a1},B=\emptyset,C={c2}$
$A={a2},B=\emptyset,C=\emptyset$
$A={a2},B={b1},C=\emptyset$
$A={a2},B=\emptyset,C={c1}$
$A={a2},B=\emptyset,C={c2}$
$A={a1,a2},B=\emptyset,C=\emptyset$
一共15种。

$Hint：It's \space just \space a \space JOKE\space!$