Ocean 和他的朋友决定通过玩老虎机来抢劫赌场。赌场里总共有 $n$ 台老虎机，玩第 $i$ 台老虎机可以赢得 $a_i$ 卢布。

Ocean 已经入侵了系统，他知道自己在每台机器上第一次尝试时都会赢，而且每台机器只能赢一次。Ocean 非常贪婪，所以他一定会每台机器都玩且仅玩一次。

然而，如果玩家在机器上赢了一次或多次，且玩家的总奖金能被 3 整除，赌场的安全系统就会认为这很可疑。Ocean 团队中的数学家想要找出有多少种玩老虎机的顺序，使得每台机器都恰好玩一次，且不被安全系统发现。由于方案数可能非常多，请输出方案数除以 $10^9 + 7$ 的余数。

输入格式

第一行包含一个整数 $n$ —— 赌场中老虎机的数量 ($1 \le n \le 10^5$)。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)。

输出格式

输出一个整数 —— 在每台机器都玩且仅玩一次的情况下，使得任何时刻的累计奖金总额都不是 3 的倍数的方案数，结果对 $10^9 + 7$ 取模。

样例

输入 1

3
100 21 892

输出 1

4

输入 2

4
11 19 30 32

输出 2

6

输入 3

3
4 298 28

输出 3

0