28931번 - Степенная башня Макса 다국어

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