该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

有 $n$ 根薯条，第 $i$ 根薯条的长度为 $a_i$。

现在你要从中选出三根薯条，并给它们组成一个"薯条小队"。为了让小队名字显得很有文化，三根薯条的长度之和必须能被 $3$ 整除。

请问有多少种不同的选择方法？

两种选择不同，当且仅当选出的薯条下标集合不同。

Format

Input

第一行一个整数 $n(3 \le n \le 2 \times 10^5)$。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n(0 \le a_i \le 10^{18})$。

Output

输出一行一个整数，表示满足条件的三元组数量。

Samples

6
1 2 3 4 5 6

8

Note

样例说明：

这些数对 $3$ 取模后的结果分别为：$1 \ 2 \ 0 \ 1 \ 2 \ 0$ 余数为 $0,1,2$ 的数各有 $2$ 个。

选择一根余数为 $0$、一根余数为 $1$、一根余数为 $2$ 的薯条即可，共有$2 \times 2 \times 2 = 8$ 种选择。