Counting Subsets with Target Sum

You are given a set of n factors (positive integers) and a target sum T. Your task is to compute the number of distinct subsets of these factors whose sum equals T. Each factor can be used at most once.

The answer may be very large, so you must compute the result modulo \(10^9+7\). Formally, if we denote by dp[i] the number of ways to achieve sum i then the recurrence is given by:

[ \text{dp}[0] = 1, \quad \text{and} \quad \text{dp}[j] = \text{dp}[j] + \text{dp}[j - f] \quad \text{for each factor } f \text{ and } j \ge f. ]

For example, if n = 3, factors = [2, 3, 5], and T = 5, there are 2 subsets with sum 5: [2, 3] and [5].

inputFormat

The first line contains a single integer n indicating the number of factors. The second line contains n space-separated integers representing the factors. The third line contains a single integer T, the target sum.

outputFormat

Output a single integer representing the number of distinct subsets whose sum equals T, taken modulo (10^9+7).## sample

3
2 3 5
5

2