Count Subsets to a Given Sum

You are given an array of positive integers and a target sum. Your task is to determine the number of distinct subsets of the array that add up exactly to the target sum. A subset is defined as any collection of the elements (not necessarily contiguous) selected from the array.

Formally, given an array (A = [a_1, a_2, \dots, a_n]) and a target (T), find the number of subsets (S \subseteq A) such that (\sum_{a \in S} a = T).

inputFormat

The input is read from standard input (stdin). It consists of three lines:

1. The first line contains an integer (n) representing the number of elements in the array.
2. The second line contains (n) space-separated integers representing the elements of the array.
3. The third line contains the target sum (T) as an integer.

outputFormat

Output the number of subsets that sum exactly to the target. The result should be printed to standard output (stdout).## sample

6
2 3 5 6 8 10
10

3