Communism

Assign each of N jobs to one of three people so that Ad's total and Larry's total differ by at most D, and count the assignments.

Hard8MathBacktrackingDynamic programmingBrute forceNo attempts yetTime limit1sMemory limit512 MB

Description

Examples2

Problem

The quiet village of Rinkaru has $N$ jobs, and they are handed out to Rinkaru, Ad and Larry. Exactly one of the three takes each job.

Ad and Larry care about fairness, so the total pay Ad takes and the total pay Larry takes must not differ by more than $D$ . The pay Rinkaru takes is under no condition.

Two ways of splitting the jobs are different when some job goes to a different person. Count the ways to split the jobs.

Input

The first line holds the number of jobs $N$ . The second line holds $N$ integers $A_1, \dots, A_N$ , the pay of each job, separated by spaces. The third line holds $D$ , the difference of the two totals that must not be exceeded. ( $1 \le N \le 30$ , $1 \le A_i \le 10^{16}$ , $0 \le D \le 10^{18}$ )

Output

Print the number of different ways to split the jobs.