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.
- All values in input are integers.
The first line will contain 2 space separated integers and .
The next line will contain integers, .
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
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
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
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