Number of Ways to Earn Points
There is a test that has n types of questions. You are given an integer target and a 0-indexed 2D integer array types where types[i] = [counti, marksi] indicates that there are counti questions of the i^th type, and each one of them is worth marksi points.
Return the number of ways you can earn exactly target points in the exam. Since the answer may be too large, return it modulo 10^9 + 7.
Note that questions of the same type are indistinguishable.
- For example, if there are
3questions of the same type, then solving the1^stand2^ndquestions is the same as solving the1^stand3^rdquestions, or the2^ndand3^rdquestions.
Example 1
Input
target = 6, types = [[6,1],[3,2],[2,3]]Output
7There are seven indistinguishable combinations of question counts across the given types that sum to exactly 6 points.
Example 2
Input
target = 5, types = [[50,1],[50,2],[50,5]]Output
4There are four ways to earn exactly 5 points: using five 1-point questions, three 1-point questions and one 2-point question, one 1-point question and two 2-point questions, or one 5-point question.
Constraints
- 1 <= target <= 1000
- n == types.length
- 1 <= n <= 50
- types[i].length == 2
- 1 <= counti, marksi <= 50