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
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial