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

Макс --- очень избалованный пёс. Недавно он выпросил у Кэти игрушечные кубики, на которых написаны числа. Он долго играл с ними, но вскоре ему это надоело. Поэтому он стал строить высокую башню из них. Сейчас в его башне $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$