Дается последовательность натуральных чисел. Гарантируется, что все числа различны. Рассматриваются всевозможные группы чисел, состоящие из любого количества элементов последовательности. Необходимо найти количество таких групп, для которых сумма элементов кратна 3.
Формат входных данных: в первой строке записано количество чисел N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит одно натуральное число, не превышающее 108.
Формат выходных данных: одно число - количество групп, для которых сумма элементов кратна 3.
Пример входных данных:
4
5
7
12
23
Выходные данные:
5
Пояснение к примеру: для указанных данных можно выбрать следующие группы: {12}; {7, 23}; {7, 12, 23}; {5, 7}; {5, 7, 12}.