Counting Coin Combinations

Difficulty: 1500 3000 ms 128 MB

dp

With unlimited coins of the given denominations, count the combinations (order does not matter) summing exactly to T, modulo 10⁹+7.

Input: the first line has N and T; the second line has the N denominations.

Output: the number of combinations mod 10⁹+7.

Constraints:

• 1 ≤ N ≤ 12
• 0 ≤ T ≤ 10⁴
• 1 ≤ c_i ≤ 100

Sample Tests

3 5
1 2 5

4

1 4
3

0

Read the Editorial