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 denominations of bank notes could he buy a Bugatti of cost 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, and . The following line consists of integers, the of which represents the value of his 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 million dollars are
- ,
- ,
- ,
- ,
- ,
- ,
- ,
- ,
- ,
- ,
- ,
- and
- .
Constraints
. That is, the value of each bank note is between 1 and 50 million dollars.
Comments