Problem Statement

You are given positive integers $N, L, R$ and length-$N$ positive integer sequences $A = (A_{1}, A_{2}, \dots, A_{N}), B = (B_{1}, B_{2}, \dots, B_{N})$.

Using a sequence $Q$ initialized as empty, a variable $C$ initialized to $0$, and a variable $i$ initialized to $1$, perform the following operation $2N$ times.

• Choose one of the following actions $1, 2$ and perform it.
• Action $1$ : Insert $i$ at the end of $Q$, replace $C$ with $\max(0, C - A_{i})$. Then, increase $i$ by $1$. This action can only be performed when $i$ before the operation is at most $N$.
  • Action $2$ : Let $x$ be the first number in $Q$, and add $B_{x}$ to $C$. Then, remove the first element of $Q$. This action can only be performed when $Q$ before the operation is not empty.

Find the number, modulo $998244353$, of ways to perform $2N$ operations such that the final value of $C$ is between $L$ and $R$, inclusive.

Constraints

• $1\leq N\leq 5000$
• $1\leq L \leq R \leq \sum B$
• $1\leq A_{i}\leq 5000$
• $1\leq B_{i}\leq 5000$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N L R
A_{1} A_{2} \dots A_{N}
B_{1} B_{2} \dots B_{N}

Output

Output the answer.