You are given n distinct positive integers called coins and a non-negative integer target. Each coin may be used any number of times (including zero). A combination is a multiset of coins whose values sum to target; two combinations are the same if they use each coin the same number of times (order does not matter).
Count how many distinct combinations sum exactly to target, and print that single number. The empty combination (using no coins) sums to 0.
Input format
Line 1: an integer n.
Line 2: n space-separated distinct positive integers, the coin values.
Line 3: an integer target.
Output format
A single integer: the number of distinct combinations of coins (with unlimited reuse) that sum to target.
Constraints
- 1 ≤ n ≤ 30
- 1 ≤ each coin value ≤ 1000
- all coin values are distinct
- 0 ≤ target ≤ 2000
- the answer fits in a 64-bit signed integer