小 $\beth$ 为了纪念停办的 codejam，准备了一场“代码堵塞纪念赛”。小 $\beth$ 的朋友小 $\mho$ 也来围观，于是小 $\beth$ 想预测小 $\mho$ 的成绩。

比赛共 $T$ 秒，有 $n$ 道题。第 $i(1\le i\le n)$ 题分数为 $a_i$，小 $\beth$ 预测小 $\mho$ 需要 $t_i$ 秒完成。

题目有两种类型：结果可见和结果不可见。结果不可见的题在比赛结束后才能知道评测结果，而结果可见的题在提交后立即得到评测结果。小 $\beth$ 还没确定每道题的类型。

小 $\mho$ 由于从不写对拍，所以会先按编号从小到大完成所有结果可见的题，再按编号从小到大完成所有结果不可见的题。小 $\mho$ 会花 $t_i$ 秒完成第 $i$ 题，当小 $\mho$ 花费在第 $i$ 题和在第 $i$ 题之前完成的所有题的时间总和不超过 $T$，就会在第 $i$ 题产生提交。

由于小 $\mho$ 提交即 AC，所以小 $\beth$ 想知道对于所有 $2^n$ 种确定 $n$ 道题类型的方案，小 $\mho$ 所能得到的分数总和的和。由于答案很大，你需要将答案对 $998244353$ 取模。

输入格式

输入的第一行包含三个整数 $c,n,T$，表示测试点编号，题数和比赛时间。样例中的 $c$ 表示其满足的限制条件与第 $c$ 个测试点一致。

输入的第二行包含 $n$ 个整数 $a_1,a_2,\cdots ,a_n$，分别表示每道题的分数。

输入的第三行包含 $n$ 个整数 $t_1,t_2,\cdots ,t_n$，分别表示小 $\mho$ 做每道题的时间。

输出格式

输出一行包含一个整数，表示对于所有确定 $n$ 道题类型的方案，小 $\mho$ 所能得到的分数总和的和，对 $998244353$ 取模。

样例 1

input

1 3 3
2 3 4
1 2 2

output

40

提示

样例 1 解释

我们用长度为 $3$ 的 $01$ 序列表示题目类型，$1$ 表示结果可见，$0$ 表示结果不可见。

• $(0,0,0)(1,0,0)(1,1,0)(1,1,1)$ 四种情况：小 $\mho$ 按照编号顺序做题，前两题产生提交，分数和为 $5$；
• $(0,1,0)$：小 $\mho$ 按照 $213$ 的顺序做题，前两题产生提交，分数和为 $5$；
• $(0,0,1)$：小 $\mho$ 按照 $312$ 的顺序做题，第一题和第三题产生提交，分数和为 $6$；
• $(1,0,1)$：小 $\mho$ 按照 $132$ 的顺序做题，第一题和第三题产生提交，分数和为 $6$；
• $(0,1,1)$：小 $\mho$ 按照 $231$ 的顺序做题，只有第二题产生提交，分数和为 $3$。

因此答案为 $(5\times 4+5+6+6+3)mod998244353=40$。

数据范围

对于所有测试数据：

• $1\le n\le 200$，
• $1\le T\le 3\times {10}^5$，
• $\mathrm{\forall }1\le i\le n,1\le a_i\le 3\times {10}^5$，
• $\mathrm{\forall }1\le i\le n,1\le t_i\le T$。

• 特殊性质 A：$\mathrm{\forall }1\le i\le n,a_i=1$。
• 特殊性质 B：$\mathrm{\forall }1\le i\le n,t_i=1$。

后记

“你们这比赛怎么所有题都结果不可见啊？”

Hack 格式

Hack 时需要保证 $c=20$。

时间限制：$\mathtt{\text{1s}}$

空间限制：$\mathtt{\text{512MB}}$