Plus or Minus

You have a row of numbers nums and a target. Put either a + or a - sign in front of every number, then add them all up. Write sign_ways(nums, target) that returns how many different ways of choosing the signs give exactly target.

Two ways are different if at least one number gets a different sign, even when the numbers are equal. A 0 can take either sign, so it doubles the count.

Examples

sign_ways([1, 2, 3], 0)     # returns 2
sign_ways([1, 1, 1, 1], 2)  # returns 4
sign_ways([4, 7], 5)        # returns 0

For [1, 2, 3] the two ways are +1 +2 -3 and -1 -2 +3. For [1, 1, 1, 1] any one of the four numbers can be the one with the minus sign.

Constraints

• 0 <= len(nums) <= 60
• 0 <= nums[i] <= 30
• -2000 <= target <= 2000

Note

With no numbers at all, the total is 0, reached in exactly one way. The count can be very large; return it exactly (Python integers have no size limit).