A company's departments form a binary tree; each node has an integer budget (which may be negative, representing a credit). The total budget of a department is the sum of the budgets of that department and all of its sub-departments (its subtree). Given a target amount, report how many departments have a total budget exactly equal to the target.
Input format
Line 1: an integer k, the number of tokens on line 2.
Line 2: k space-separated tokens giving the tree in level order. The first token is the root; each subsequent token is an integer budget or null for a missing child. Children of null nodes are omitted.
Line 3: an integer target.
Output format
A single integer: the number of departments whose total budget equals target.
Constraints
- The tree has between 1 and 2000 nodes (the root is always present).
- Each budget is between -1000000 and 1000000.
targetis between -2000000000 and 2000000000.