Max's Power Tower

Interview

Time limit2sMemory limit1024 MB

Summary

Given a right-associative power tower of n natural numbers, find its value modulo 3.

Level: Medium4 of 10
Topics: Math, Number theory
Solved: No attempts yet

Problem

Max is a very spoiled dog. Recently he begged Katy for a set of toy cubes with numbers written on them. He played with them for a while, then got bored and started stacking them into a tall tower.

The tower has $n$ cubes, and each cube has a natural number $a_i$ written on it. Max wants to know the value of the power tower $a_1^{a_2^{a_3^{\dots^{a_n}}}}$ . He cannot keep large numbers in his head, so he wants the result modulo 3. Help Max.

Exponentiation is right-associative.

Input

The first line contains a natural number $n$ ( $1 \le n \le 10^5$ ). The next line contains $n$ natural numbers $a_i$ ( $1 \le a_i \le 10^9$ ).

Output

Print the value of $a_1^{a_2^{a_3^{\dots^{a_n}}}} \bmod 3$ .

Hint

In the second test case, $2^{3^2} = 512 \bmod 3 = 2$ .

Examples2

Example 1
Input
```
3
1 2 3
```
Expected output
```
1
```
Example 2
Input
```
3
2 3 2
```
Expected output
```
2
```