18609번 - Square Root Partitioning 다국어

문제

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.

제한

힌트