## Educational DP Contest AtCoder M - Candies

View as PDF

Points: 12
Time limit: 1.0s
Memory limit: 1G

Problem type

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