603. Build an Expression

0

Medium

You are given an integer array nums and an integer target.
You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.
For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1".
Print the number of different expressions that you can build, which evaluates to target.

Input Format

First line contains size of array

Second line contains elements of Array

Third line contains target

Second line contains elements of Array

Third line contains target

Output Format

Print the number of different expressions (Integer)

Example

Input

5
1 1 1 1 1
3

Output

5

Constraints

1 <= nums.length <= 20

0 <= nums[i] <= 1000

0 <= sum(nums[i]) <= 1000

-1000 <= target <= 1000

0 <= nums[i] <= 1000

0 <= sum(nums[i]) <= 1000

-1000 <= target <= 1000

Loading...

View Submissions

Console