题目描述

定义一种新的二元运算 ++：对于两个正整数 $a$ 和 $b$，$a\text{++}b$ 表示将 $a$ 的十进制数字与 $b$ 的十进制数字按顺序拼接形成的新正整数。例如：

• $123\text{++}123 = 123123$
• $14\text{++}2 = 142$
• $5\text{++}678 = 5678$

现在给定 $n$ 个正整数，记为数组 $\text{nums} = [\text{num}_1, \text{num}_2, \dots, \text{num}_n]$。请你计算有多少种选法满足以下条件：

1. 选取的两个数为 $\text{nums}$ 中位置不同的两个元素（即选取第 $i$ 个元素和第 $j$ 个元素，其中 $i \neq j$）；
2. 这两个数进行 ++ 操作的结果（即 $\text{nums}[i]\text{++}\text{nums}[j]$）是 3 的倍数；
3. 选法为无序对：选取第 $i$ 个元素和第 $j$ 个元素，与选取第 $j$ 个元素和第 $i$ 个元素视为同一种选法（仅需计数一次）。

输入格式

第一行输入一个整数 $n$，表示正整数的个数。 第二行输入 $n$ 个用空格分隔的正整数 $\text{num}_1, \text{num}_2, \dots, \text{num}_n$。

输出格式

输出一个整数，表示满足条件的选法总数。

样例输入 1

3
1 2 3

样例输出 1

1

样例解释 1

我们只需要统计“选第一个数和第二个数、选第一个数和第三个数、选第二个数和第三个数”这3种无序选法：

• 选1和2：拼接结果是12，12能被3整除（12÷3=4），符合条件，计入；
• 选1和3：拼接结果是13，13不能被3整除（13÷3余1），不计入；
• 选2和3：拼接结果是23，23不能被3整除（23÷3余2），不计入。

总计1种符合条件的选法。

样例输入 2

2
3 6

样例输出 2

1

样例解释 2

只有1种无序选法：选3和6。 拼接结果是36，36能被3整除（36÷3=12），符合条件，计入。

总计1种符合条件的选法。

样例输入 3

4
4 5 6 7

样例输出 3

2

样例解释 3

所有无序选法共6种，其中符合条件的有2种：

• 选4和5：拼接结果是45，45能被3整除（45÷3=15），计入；
• 选5和7：拼接结果是57，57能被3整除（57÷3=19），计入； 其余选法（4和6、4和7、5和6、6和7）的拼接结果均不能被3整除，不计入。

总计2种符合条件的选法。

数据范围与提示

• 对于 $40\%$ 的数据，$1 \le n \le 10^3$，$1 \le \text{num}_i \le 10^{4}$；
• 对于 $80\%$ 的数据，$1 \le n \le 10^6$，$1 \le \text{num}_i \le 10^{8}$；
• 对于 $100\%$ 的数据，$1 \le n \le 10^6$，$1 \le \text{num}_i \le 10^{30}$；