SOLVE

LATER

Accommodation

/

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.

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

Initializing Code Editor...