Counting Subsets with Given Sum

Difficulty: 1600 5000 ms 128 MB

dp knapsack

Count the subsets of the given multiset whose elements sum to exactly T, modulo 10⁹+7.

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

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

Constraints:

• 1 ≤ N ≤ 2000
• 1 ≤ T ≤ 3000
• 1 ≤ a_i ≤ T

Sample Tests

3 4
1 3 4

2

2 5
2 3

1

1 1
1

1

Read the Editorial