맥스의 거듭제곱 탑

면접 대비

시간 제한2초메모리 제한1024 MB

요약

오른쪽 결합 거듭제곱 탑 a1^(a2^(...^an))의 값을 3으로 나눈 나머지를 구합니다.

난이도: 보통10점 중 4점
유형: 수학, 정수론
정답자: 아직 제출이 없습니다

문제

맥스는 매우 버릇없는 개다. 최근 케이티에게 숫자가 적힌 장난감 큐브를 졸라서 받았다. 한동안 가지고 놀았지만 곧 싫증이 나서, 큐브로 높은 탑을 쌓기 시작했다.

탑에는 $n$ 개의 큐브가 있고, 각 큐브에는 자연수 $a_i$ 가 적혀 있다. 맥스는 거듭제곱 탑 $a_1^{a_2^{a_3^{\dots^{a_n}}}}$ 의 값이 궁금하다. 하지만 큰 수를 머릿속에 담아 둘 수 없으므로, 이 값을 3으로 나눈 나머지로 알고 싶어 한다. 맥스를 도와주자.

거듭제곱은 오른쪽 결합 연산이다.

입력

첫 줄에 자연수 $n$ ( $1 \le n \le 10^5$ )이 주어진다. 다음 줄에는 자연수 $a_i$ ( $1 \le a_i \le 10^9$ )가 $n$ 개 주어진다.

출력

$a_1^{a_2^{a_3^{\dots^{a_n}}}} \bmod 3$ 의 값을 출력한다.

힌트

두 번째 테스트 케이스에서 $2^{3^2} = 512 \bmod 3 = 2$ 이다.

예제2

예제 1
입력
```
3
1 2 3
```
예상 출력
```
1
```
예제 2
입력
```
3
2 3 2
```
예상 출력
```
2
```