All Tracks Algorithms Dynamic Programming Introduction to Dynamic Programming 1 Problem


Algorithms, Dynamic Programming


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.

3 5
1 2 3

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

Best Submission

Similar Problems


This Problem was Asked in

Initializing Code Editor...
View All Notifications