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 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
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).
