Макс — очень избалованный пёс. Недавно он выпросил у Кэти игрушечные кубики, на которых написаны числа. Он долго играл с ними, но вскоре ему это надоело. Поэтому он стал строить высокую башню из них. Сейчас в его башне n кубиков, на каждом из которых написано некоторое натуральное число ai. Максу стало интересно, чему равно значение степенной башни a1a2{a3...}an. Но так как Макс пёс, то больших чисел удержать в голове он не может, поэтому он хочет узнать результат по модулю 3. Помогите Максу.
Напомним, что операция возведение в степень правоассоциативна.
В первой строке находится натуральное число n (1 ≤ n ≤ 105). В следующей строке находится n натуральных чисел ai (1 ≤ ai ≤ 109).
Выведите результат выражения
3
1 2 3
1
3
2 3 2
2
Во втором тестовом примере