SOLVE
LATER
You are given n numbers x_{1},x_{2},...,x_{n} and a prime number P. Count the number of tuples (y_{1},...,y_{n}) with 0 ≤ y_{i} ≤ x_{i} 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.
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 x_{i}.
A single integer, the number of tuples modulo 10^9+7.
For all subtasks:
P is prime
1≤ x_{i}
2 ≤ P
Subtask 1 (29 pts):
n = 2
x_{i} ≤ 100
P ≤ 50
Subtask 2 (27 pts):
n ≤ 11
x_{i} ≤ 1,000,000,000
P ≤ 100
Subtask 3 (23 pts):
n = 2
x_{i} ≤ 1,000,000,000
P ≤ 1,000,000
Subtask 4 (21 pts):
n ≤ 11
x_{i} ≤ 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).