There is a hotel with M floors. $i^{th}$ floor of the hotel has infinite identical rooms, each room can accommodate $C[i]$ people (Two rooms of same floor are indifferentiable and have same capacity while two rooms of different floors have different capacity).
There is one rule:
Any room on $i^{th}$ floor will accommodate exactly $C[i]$ people (not less or more).

Now N identical people come for accommodation. You can assign any of them to any room of any floor following the mentioned rule.

Way of assigning:
If we have 5 people and 3 floors. Let's say floor 1 has room capacity 1 and floor 2 has room capacity 2, then:
(1,2,2) is a way of assigning people. This means we assign one person out of those 5 people to any room of floor 1. The remaining 4 people are assigned to two rooms of floor 2, each room accommodating 2 people.
We will consider (1,2,2), (2,1,2), (2,2,1) as the same ways as we can't differentiate between them.

You have to tell number of different ways of accommodating N people.
Two ways are considered different if one way is not a permutation of other way.

Input Format:
First line consists of two integers M and N, denoting number of floors and number of people respectively.
Second line consists of M space separated integers denoting capacity of floors. $i^{th}$ integer denotes capacity of $i^{th}$ floor.

Output Format:
Print the number of different ways of accommodating people.
Since the number of ways can be large, print the answer modulo $10^9+7$.

Input Constraints:
$1 \le N * M \le 10^6$
$1 \le C[i] \le 10^6$
All $C[i]$ are different.