Count Distinct Subsets

Given an array of integers and a target sum \(S\), your task is to count the number of distinct subsets (each subset must contain at least one element) of the array that add up exactly to \(S\). Two subsets are considered the same if they contain the same elements regardless of order.

For example, if the array is [2, 3, 5, 7] and \(S = 10\), the valid subsets are \(\{3, 7\}\) and \(\{2, 3, 5\}\), so the answer is 2.

Note that the array might contain duplicate elements. However, subsets that are rearrangements of each other are counted only once.

inputFormat

The input is given in the following format from standard input (stdin):

1. An integer \(n\) representing the number of elements in the array.
2. \(n\) space-separated integers representing the elements of the array.
3. An integer \(S\) representing the target sum.

For example:

4
2 3 5 7
10

outputFormat

Output to standard output (stdout) a single integer that represents the number of distinct subsets whose sum is exactly \(S\).

For example, for the input above, the output should be:

2

## sample

4
2 3 5 7
10

2

</p>