Bob is investigating properties of integer sequences in an attempt to solve George's least favourite problem: Maintaining A Sequence!

To help Bob achieve his dreams, George gives Bob a warm up problem:

How many ordered sequences of non-negative integers are such that each element is a member of the set and whose sum is at most ?

Bob points out that this number might be a bit large, so George lets him return the answer modulo .

Can you help Bob solve his warm up problem?

#### Constraints

For all subtasks, .

The 's are guaranteed to be pairwise distinct.

##### Subtask 1 [20%]

##### Subtask 2 [20%]

for all

##### Subtask 3 [20%]

##### Subtask 4 [40%]

#### Input Specification

The first line of input will contain three space separated integers, , , and .

The second line of input will contain space-separated integers, .

#### Output Specification

The number of sequences that satisfy the given conditions, modulo .

#### Sample Input

```
2 3 4
1 3 2 0
```

#### Sample Output

`10`

#### Explanation for Sample

The possible sequences are: , , , , , , , , , and .

## Comments