Степенная башня Макса
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
powerstower.in
вывод
powerstower.out

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

Примечание

Во втором тестовом примере