To commemorate the discontinuation of Codejam, Xiao has prepared a "Codejam Memorial Contest." Xiao's friend also came to watch, so Xiao wants to predict their performance.

The contest lasts $s$ seconds and consists of $n$ problems. The $i$-th problem ($1 \le i \le n$) has a score of $a_i$, and Xiao predicts that it will take $t_i$ seconds to complete.

There are two types of problems: visible-result and hidden-result. The evaluation result of a hidden-result problem is only known after the contest ends, while the result of a visible-result problem is known immediately after submission. Xiao has not yet determined the type of each problem.

Since Xiao never writes checkers, they will first complete all visible-result problems in increasing order of their indices, and then complete all hidden-result problems in increasing order of their indices. Xiao spends $t_i$ seconds to complete the $i$-th problem. If the total time spent on the $i$-th problem and all problems completed before it does not exceed $s$, a submission is generated for the $i$-th problem.

Since Xiao's submissions are always AC, Xiao wants to know the sum of the total scores of all problems for which a submission is generated, across all $2^n$ possible ways to assign the type of each of the $n$ problems. Since the answer can be very large, you need to output the answer modulo $998244353$.

Input

The first line contains three integers $id$, $n$, and $s$, representing the test case ID, the number of problems, and the contest duration. The $id$ in the sample indicates that its constraints are consistent with the test case with that ID.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$, representing the score of each problem.

The third line contains $n$ integers $t_1, t_2, \dots, t_n$, representing the time required to complete each problem.

Output

Output a single integer representing the sum of the total scores of all problems for which a submission is generated, across all $2^n$ possible ways to assign the problem types, modulo $998244353$.

Examples

Input 1

1 3 3
2 3 4
1 2 2

Output 1

40

Note 1

We use a binary sequence of length 3 to represent the problem types, where 1 means visible-result and 0 means hidden-result.

• $(0, 0, 0), (1, 0, 0), (1, 1, 0), (1, 1, 1)$ (four cases): Xiao completes the problems in index order, the first two problems generate submissions, and the sum of scores is 5.
• $(0, 1, 0)$: Xiao completes the problems in the order 2, 1, 3, the first two problems generate submissions, and the sum of scores is 5.
• $(0, 0, 1)$: Xiao completes the problems in the order 3, 1, 2, the first and third problems generate submissions, and the sum of scores is 6.
• $(1, 0, 1)$: Xiao completes the problems in the order 1, 3, 2, the first and third problems generate submissions, and the sum of scores is 6.
• $(0, 1, 1)$: Xiao completes the problems in the order 2, 3, 1, only the second problem generates a submission, and the sum of scores is 3.

Therefore, the answer is $(5 \times 4 + 5 + 6 + 6 + 3) \pmod{998244353} = 40$.

Examples 2-5

See the files 2.in and 2.ans, 3.in and 3.ans, 4.in and 4.ans, 5.in and 5.ans in the problem directory. These samples satisfy $id = 7, 13, 16, 20$ respectively.

Constraints

For all test data: $1 \le n \le 200$ $1 \le s \le 3 \times 10^5$ $\forall 1 \le i \le n, 1 \le a_i \le 3 \times 10^5$ $\forall 1 \le i \le n, 1 \le t_i \le s$

Special Property A: $\forall 1 \le i \le n, a_i = 1$. Special Property B: $\forall 1 \le i \le n, t_i = 1$.

Postscript

"Why are all the problems in this contest hidden-result?"