Bugatti (Redux)

View as PDF

Submit solution

Points: 100
Time limit: 1.0s
Python 3 10.0s
Memory limit: 256M

Author:
Problem type

The following is the problem statement for the problem Bugatti. The differences between this problem and Bugatti are in the third paragraph.

After becoming CEO of Hoptiver, Andy is now a millionare! Unsure what to do with all his newfound wealth, Andy decides to buy a Bugatti like his favourite influencer.

However, in his infinite wealth Andy only owns banknotes worth multiples of million dollars. Andy wonders, with how many different combinations of his n denominations of bank notes could he buy a Bugatti of cost k million dollars.

Now, Andy wants to consider a slightly different problem. How many different orderings of bank notes could he use to buy his Bugatti? For example 1,1,2 is considered different to 1,2,1 in this problem. Furthermore, Andy now wants to buy a super Bugatti, which is considerably more expensive. Will he be able to escape the matrix? (wink)

Input Format

The input will consist of two lines. The first line has two space-separated integers, n and k. The following line consists of n integers, the ith of which represents the value of his ith type of bank note, in millions of dollars. These values will be distinct.

Output Format

The output should consist of a single integer, representing the number of combinations. Since there could be many combinations, output this value modulo 1e9+7.

Sample Input

3 5
1 2 3

Sample Output

13

Sample Explanation

The combinations that sum to 5 million dollars are

  • 1+1+1+1+1,
  • 1+1+1+2,
  • 2+1+1+1,
  • 1+2+1+1,
  • 1+1+2+1,
  • 3+1+1,
  • 1+3+1,
  • 1+1+3,
  • 2+1+2,
  • 2+2+1,
  • 1+2+2,
  • 3+2 and
  • 2+3.

Constraints

1 \le n \le 50

1 \le a[i] \le 50. That is, the value of each bank note is between 1 and 50 million dollars.

1 \le k \le 1e15


Comments

There are no comments at the moment.