부분집합 합의 XOR

정수 $n$개 $A_1, A_2, \dots, A_n$이 주어진다. $N = \{1, 2, \dots, n\}$이라고 하자.

$N$의 부분집합 $I$에 대해 $S_I$를 다음과 같이 정의한다.

$S_I = \sum_{k \in I} A_k$

즉 $I$에 속한 첨자 $k$의 $A_k$를 모두 더한 값이다. 공집합의 합은 0이고, $N$ 자신도 부분집합으로 센다. 그러므로 $S_I$는 모두 $2^n$개다.

이 $2^n$개의 값을 전부 비트 단위 배타적 논리합(XOR)한 결과를 $X$라고 하자.

$X = \bigoplus_{I \subseteq N} S_I$

$X$를 구하라.

첫째 줄에 $n$이 주어진다. ($1 \le n \le 30$)

둘째 줄에 $n$개의 정수 $A_1, A_2, \dots, A_n$이 공백으로 구분되어 주어진다. ($0 \le A_i < 2^{30}$)

첫째 줄에 $X$를 출력한다.