All problems

Postage with Every Design

Medium · dynamic programming

A post office sells commemorative stamps in several designs. Design i is worth values[i] pence, and the shop has as many stamps of each design as you could want. Two designs may have the same value; they still count as different designs.

A collector wants to send a parcel with postage of exactly postage pence. To make the parcel a showpiece, it must carry at least one stamp of every design.

Two ways to cover the parcel are different when some design is used a different number of times. The order in which the stamps are stuck on does not matter.

Return the number of different ways, modulo 10^9 + 7. If the postage cannot be made, return 0.

Examples

Example 1

Input: values = [2, 3], postage = 10

Output: 1

Two stamps of the first design and two of the second give 4 + 6 = 10. Every other count would leave a design out or miss 10.

Example 2

Input: values = [1, 1], postage = 4

Output: 3

The two designs can be used (1, 3), (2, 2) or (3, 1) times.

Example 3

Input: values = [5, 7], postage = 10

Output: 0

One of each already costs 12, which is more than 10.

Constraints