Problem Description
You are given a set of coins A. In how many ways can you make sum B assuming you have an infinite amount of each coin in the set.
Note: Coins in set A will be unique. The expected space complexity of this problem is O(B).
Note that the answer can overflow. So, give us the answer % 1000007
Problem Constraints
1 <= |A| <= 500
1 <= B <= 5 * 104
Input Format
The first argument is an integer array A.
The second argument is an integer B.
Output Format
Return the answer % 1000007
Example Input
A = [1, 2, 3]
B = 4
Example Output
4
Example Explanation
The 4 possible ways are
{1, 1, 1, 1}
{1, 1, 2}
{2, 2}
{1, 3}
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified.
Still have a question? Checkout Sample Codes for more details.