There are children, numbered .

They have decided to share candies among themselves. Here, for each , Child must receive between and candies (inclusive). Also, no candies should be left over.

Find the number of ways for them to share candies, modulo . Here, two ways are said to be different when there exists a child who receives a different number of candies.

#### Constraints

- All values in input are integers.

#### Input Specification

The first line will contain 2 space separated integers and .

The next line will contain integers, .

#### Output Specification

Print the number of ways for the children to share candies, modulo .

**Note:** Be sure to print the answer modulo .

#### Sample Input 1

```
3 4
1 2 3
```

#### Sample Output 1

`5`

#### Explanation for Sample 1

There are five ways for the children to share candies, as follows:

Here, in each sequence, the -th element represents the number of candies that Child receives.

#### Sample Input 2

```
1 10
9
```

#### Sample Output 2

`0`

#### Explanation for Sample 2

There may be no ways for the children to share candies.

#### Sample Input 3

```
2 0
0 0
```

#### Sample Output 3

`1`

#### Explanation for Sample 3

There is one way for the children to share candies, as follows:

#### Sample Input 4

```
4 100000
100000 100000 100000 100000
```

#### Sample Output 4

`665683269`

## Comments