406310: GYM102354 A Square Root Partitioning

Memory Limit:0 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A. Square Root Partitioningtime limit per test3 secondsmemory limit per test256 mebibytesinputstandard inputoutputstandard 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.

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

加入题单

上一题 下一题 算法标签: