You are given n positive integers and a target t. Count the number of subsets (chosen by index, so equal values at different positions are different elements) whose elements sum to exactly t. The empty subset has sum 0.
Input format
Line 1: an integer n.
Line 2: n space-separated positive integers.
Line 3: the target t.
Output format
A single integer: the number of subsets summing to t.
Constraints
- 1 <= n <= 18
- 1 <= each value <= 100
- 0 <= t <= 100000