糖度

题目描述

可爱和糖, 区别只在一念之间.

奶龙的形象可爱, 深受大朋友和小朋友的喜爱, 现在某公司要设计一个新的卡通形象。有 $N$ 种设计元素，每种元素都有一个糖度值 $S$。

显然, 每个元素只能选择使用或是不使用, 而且不能什么元素都不使用 (至少采用一种设计元素).

我们认为, 卡通形象的糖度是所选用的设计元素的糖度和, 当这个糖度为 $3$ 的倍数的时候, 我们认为这个形象是可爱的, 否则就是糖的.

请计算有多少种不同的选择设计元素的方案, 使得设计出来的形象是可爱的而不是糖的。注意这里不同方案的指: 在某个方案中使用的元素在另一个方案中没有使用.

输入格式

第一行包含一个整数 $N$，表示设计元素数量。

第二行包含 $N$ 个整数，表示每种设计元素的糖度值 S。

输出格式

输出仅包含一个数字，为设计元素选择方案的数量。答案对 $1e9 + 7$ 取模。

样例 #1

样例输入 #1

4
1 2 3 6

样例输出 #1

7

样例解释

有七种可行的组合方案：

1. 使用第一种和第二种元素（总糖度为1+2=3）
2. 使用第一、二、三种元素（总糖度为1+2+3=6）
3. 使用第一、二、四种元素（总糖度为1+2+6=9）
4. 使用第三种元素（糖度为3）
5. 使用第三、四种元素（总糖度为3+6=9）
6. 使用第四种元素（糖度为6）
7. 使用第一、二、三、四种元素（总糖度为1+2+3+6=12）

每一种方案的总糖度都是3的倍数，符合题目要求。此外，所有方案中都至少使用了一种元素。

数据范围

• $1 \leq N \leq 10^5$
• $1 \leq S \leq 10^6$