Some students in KSA tend to work hard only on their preferred subjects. Assume that there are $N$ subjects $1, 2, \cdots, N$ to study, and let a nonnegative integer $s_i$ represent the amount of study needed for the subject $i$.
For each $i$, Minu wants to study subject $i$ at least as much as the subject $A_i$. That is, $s_i \geq s_{A_i}$. ($A_i$ can be $i$.)
He thinks that his total grade is proportional to the value of $\sum_{i=1}^N B_i s_i$. Since he doesn't want to blow the exam nor study too much, he wants to make sure that $X \leq \sum_{i=1}^N B_i s_i \leq Y$ holds.
Given the value of $N$, $X$, $Y$, $A_1, \cdots, A_N$, and $B_1, \cdots, B_N$, find the number of study plans.
More formally, find the number of the sequences $s$ satisfying the following conditions:
- The length of the sequence is $N$ and it consists of nonnegative integers.
- $s_i \geq s_{A_i}$.
- $X \leq \sum_{i=1}^N B_i s_i \leq Y$.
Input
The first line contains three space-separated integers $N$, $X$, and $Y$.
The second line contains $N$ space-separated integers $A_1, A_2, \cdots, A_N$.
The third line contains $N$ space-separated integers $B_1, B_2, \cdots, B_N$.
Output
Print the answer, modulo $998\,244\,353$.
Constraints
- $1 \leq N \leq 1000$
- $1 \leq X \leq Y \leq 10^5$
- $1 \leq A_i \leq N$
- $1 \leq B_i \leq 10^5$
Scoring
| No. | Points | Constraints |
|---|---|---|
| 1 | 10 | $A_i = i$ |
| 2 | 19 | $A_i = \min(i+1, N); Y \leq 100$ |
| 3 | 22 | $Y \leq 100$ |
| 4 | 25 | $A_i = \min (i+1, N)$ |
| 5 | 28 | No additional constraints |
Examples
Input 1
3 12 15 1 2 3 3 5 7
Output 1
9
Input 2
3 19 19 2 3 3 1 2 4
Output 2
14