You are given n numbers x₁,x₂,...,x_n and a prime number P. Count the number of tuples (y₁,...,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.

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

Output format:

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

Constraint:

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