- Prepare
- Algorithms
- Dynamic Programming
- Counting the Ways

# Counting the Ways

# Counting the Ways

Little Walter likes playing with his toy scales. He has types of weights. The weight type has weight . There are infinitely many weights of each type.

Recently, Walter defined a function, , denoting the number of different ways to combine several weights so their total weight is equal to . Ways are considered to be different if there is a type which has a different number of weights used in these two ways.

For example, if there are types of weights with corresonding weights , , and , then there are ways to get a total weight of :

- Use weights of type .
- Use weights of type .
- Use weight of type and weight of type .
- Use weight of type .

Given , , , and , can you find the value of ?

**Input Format**

The first line contains a single integer, , denoting the number of types of weights.

The second line contains space-separated integers describing the values of , respectively

The third line contains two space-separated integers denoting the respective values of and .

**Constraints**

**Note:** The time limit for C/C++ is second, and for Java it's seconds.

**Output Format**

Print a single integer denoting the answer to the question. As this value can be very large, your answer must be modulo .

**Sample Input**

```
3
1 2 3
1 6
```

**Sample Output**

```
22
```

**Explanation**