Степенная башня Макса

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

요약

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

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

문제

Макс --- очень избалованный пёс. Недавно он выпросил у Кэти игрушечные кубики, на которых написаны числа. Он долго играл с ними, но вскоре ему это надоело. Поэтому он стал строить высокую башню из них. Сейчас в его башне $n$ кубиков, на каждом из которых написано некоторое натуральное число $a\_i$ . Максу стало интересно, чему равно значение степенной башни $a\_1^{a\_2^{{a\_3 \dots}^{a\_n}}}$ . Но так как Макс пёс, то больших чисел удержать в голове он не может, поэтому он хочет узнать результат по модулю 3. Помогите Максу.

Напомним, что операция возведение в степень правоассоциативна.

입력

В первой строке находится натуральное число $n$ ( $1 \le n \le 10^5$ ). В следующей строке находится $n$ натуральных чисел $a\_i$ ( $1 \le a\_i \le 10^9$ ).

출력

Выведите результат выражения $a\_1^{a\_2^{{a\_3 \dots}^{a\_n}}} \mod 3$

힌트

Во втором тестовом примере $2^{3^2} = 512 \mod 3 = 2$

예제2

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