E. Casino
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Ocean and his friends decided to rob a casino by playing the slot machines. There are a total of $$$n$$$ slot machines in the casino, and playing on the $$$i$$$-th machine will yield a win of $$$a_{i}$$$ rubles.

Ocean has hacked the system and knows that he will win on each machine on the first try, but only once. Ocean is very greedy, so he will definitely play exactly once on each machine.

However, the casino's security system considers it suspicious if a player wins one or more times on the machines and the total winnings of the player are divisible by $$$3$$$. The mathematician in Ocean's team wants to find the number of ways to choose the order of the machines to play on each machine exactly once and remain undetected by the security system. Since there can be very many ways, output the remainder of the number of ways divided by $$$10^{9} + 7$$$.

Input

The first line contains a single integer $$$n$$$ — the number of machines in the casino ($$$1 \le n \le 10^{5}$$$).

The second line contains $$$n$$$ integers $$$a_{1}, a_{2}, \ldots, a_{n}$$$ ($$$1 \le a_{i} \le 10^{9}$$$).

Output

Output a single integer — the number of ways to play on each machine exactly once, without ever having a positive total win that is a multiple of $$$3$$$, taken modulo $$$10^{9} + 7$$$.

Examples
Input
3
100 21 892
Output
4
Input
4
11 19 30 32
Output
6
Input
3
4 298 28
Output
0