Question

Number of Groups

4

1 2 3 5

4

There are only 4 possible groups: (1,2,3);

(1,2) ; (1,5) ; (1,3,5)

3

1 1 1

1

There is only 1 possible group: (1,1,1).

Given an array **arr[]** of **n** distinct integers. Find the count of groups of **2 or 3** integers that can be formed by choosing integers from the given array such that sum of integers in each of the group is divisible by three.

**NOTE: **Answer can be very large.

Input

The first line of input will take an integer as input representing

The second line of input will take

1 ≤ n ≤ 10

1 ≤ arr[i] ≤ 10

**n**.The second line of input will take

**n**space-separated integers representing elements of array**arr**.**Constraints:**1 ≤ n ≤ 10

^{5}1 ≤ arr[i] ≤ 10

^{5}Output

Print an integer representing a count of groups of 2 or 3 integers that can be formed by choosing integers from the given array such that the sum of integers in each of the groups is divisible by three.

**NOTE:**Answer can be very large.Example

**Input:**

4

1 2 3 5

**Output:**

4

**Explanation:**

There are only 4 possible groups: (1,2,3);

(1,2) ; (1,5) ; (1,3,5)

**Input:**

3

1 1 1

**Output:**

1

**Explanation:**

There is only 1 possible group: (1,1,1).