Accommodation
/

## Algorithms, Dynamic Programming

Problem
Editorial
Analytics

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.

SAMPLE INPUT
3 5
1 2 3

SAMPLE OUTPUT
5

Explanation

We can assign as follows:
(1,1,1,1,1) : assign each of the 5 people to rooms of first floor.
(1,1,1,2) : assign 3 people to rooms of first floor of, 2 people to room on second floor.
(1,1,3) : assign 2 people to rooms of first floor, 3 people to room of third floor.
(1,2,2) : assign 4 people to rooms of second floor with each room having 2 people, 1 person to room of first floor.
(2,3) : assign 2 people to room of second floor, 3 people to room of third floor.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...