You are given n numbers x1,x2,...,xn and a prime number P. Count the number of tuples (y1,...,yn) with 0 ≤ yi ≤ xi and
$\displaystyle\binom{y_1+y_2+\ldots+y_n}{y_1,y_2,\ldots,y_n}$ divisible by P. (Multinomial coefficents)

Since this number can get very large, return the count modulo 10^9+7.

Input format:
The first line of input will contain two integers n, P.
The second line of input will contain n integers. The i-th integer on this line is xi.

Output format:
A single integer, the number of tuples modulo 10^9+7.

Constraint:
For all subtasks:
P is prime
1≤ xi
2 ≤ P

Subtask 1 (29 pts):
n = 2
xi ≤ 100
P ≤ 50

Subtask 2 (27 pts):
n ≤ 11
xi ≤ 1,000,000,000
P ≤ 100

Subtask 3 (23 pts):
n = 2
xi ≤ 1,000,000,000
P ≤ 1,000,000

Subtask 4 (21 pts):
n ≤ 11
xi ≤ 1,000,000,000
P ≤ 1,000,000

SAMPLE INPUT
4 3
1 3 2 4

SAMPLE OUTPUT
76

Explanation

We want to find the number of 4-tuples where the first element is between 0 and 1, the second is between 0 and 3, the third is between 0 and 2, and the last is between 0 and 4 such that the multinomial coefficient is divisible by 3. Some examples of tuples that satisfy these constraints are (0,0,1,2), (1,1,1,0), (1,3,2,4).

见题面

见题面