You are given n non-negative integers in a fixed order and a target integer t. In front of each number you must write either a + or a - sign, then add everything up. Count the number of sign assignments whose signed total is exactly t.
Every number receives a sign, and a +0 and a -0 are considered different sign choices (so zeros still double the count).
Input format
Line 1: an integer n.
Line 2: n space-separated non-negative integers.
Line 3: the target integer t (may be negative).
Output format
A single integer: the number of sign assignments whose signed total equals t.
Constraints
- 1 <= n <= 18
- 0 <= each value <= 100
- -100000 <= t <= 100000