Square Root Partitioning

시간 제한3초메모리 제한512 MB

요약

n개의 제곱근에 부호를 붙여 합이 정확히 0이 되는 경우의 수를 구한다.

문제

Consider the following expression:

\[\sqrt{a_1} \pm \sqrt{a_2} \pm \cdots \pm \sqrt{a_n} = 0\text{.}\]

Calculate the number of ways to replace each \(\pm\) with \(+\) or \(-\) so that it holds true.

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

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

Output a single integer: the answer to the problem.