제곱근 분할

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

요약

n개의 수(n은 36 이하, 값은 10^100000 이하)가 주어질 때, 각 제곱근에 + 또는 -를 붙여 합이 0이 되는 방법의 수를 구합니다.

문제

다음 식을 생각해 보자.

$\sqrt{a_1} \pm \sqrt{a_2} \pm \cdots \pm \sqrt{a_n} = 0.$

각 $\pm$ 기호를 $+$ 또는 $-$ 로 바꾸어 식이 성립하도록 하는 방법의 수를 구하라.

첫째 줄에 정수 $n$ ( $2 \le n \le 36$ )이 주어진다.

둘째 줄에 정수 $a_1, a_2, \dots, a_n$ ( $1 \le a_i \le 10^{10^5}$ )이 주어진다.

답을 나타내는 정수 하나를 출력한다.