A. Square Root Partitioning
time limit per test
3 seconds
memory limit per test
256 mebibytes
input
standard input
output
standard output

Consider the following expression: $$$$$$\sqrt{a_1} \pm \sqrt{a_2} \pm \dots \pm \sqrt{a_n} = 0\text{.}$$$$$$ Calculate the number of ways to replace each $$$\pm$$$ with $$$+$$$ or $$$-$$$ so that it holds true.

Input

The first line of input contains a single integer $$$n$$$ ($$$2 \leq n \leq 36$$$).

Second line of input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^{10^5}$$$).

Output

Output a single integer: the answer to the problem.

Examples
Input
3
2 2 8
Output
1
Input
4
4 9 25 49
Output
0