Coin Change II

In how many different ways can you make amount using coins of the given distinct denominations (unlimited supply of each)? Ways that use the same coins in a different order count once (1 + 2 and 2 + 1 are the same way). Print the answer modulo 1 000 000 007.

Input:

• line 1: n amount
• line 2: n distinct coin values

Output: the number of ways modulo 10⁹ + 7 (amount = 0 has exactly one way: no coins).

Constraints: 1 ≤ n ≤ 300, 1 ≤ coin ≤ 5000, 0 ≤ amount ≤ 5000.

Think about it: ways[a] += ways[a − coin], with the loop over coins outside and amounts inside — that order counts combinations. Swap the loops and you count ordered sequences instead (a classic bug!).