Professor Mile has a collection of N exam questions where each question is worth a certain number of points P_i, 1 ≤ i ≤ N. Professor Mile is a very superstitious person and he believes that the numbers 4 and 6 are his lucky numbers. Therefore at each exam he employs the following scenario:

There are exactly 4 students taking the exam and he chooses a set of 6 questions from his collection for the students to answer. The professor wants to choose the set of questions so he will be able to distribute them to the students in a way that each question is given to exactly one student and the total points of the question(s) each student has are equal.

So, for questions which are worth:
      Question 1: 2 points
      Question 2: 2 points
      Question 3: 4 points
      Question 4: 5 points
      Question 5: 3 points
      Question 6: 3 points
      Question 7: 5 points

Professor Mile can choose Question 1, Question 2, Question 4, Question 5, Question 6 and Question 7 i.e. we can write that he can choose the set of questions: {1,2,4,5,6,7}.

One possible distribution in which Mile can distribute these questions to the students is by giving Questions 1 and 5 to one student (the total points are equal to 2+3=5), giving Question 4 to another student (the total points are equal to 5=5), Question 7 to another student (the total points are equal to 5=5), and Questions 2 and 6 to the last/fourth student (the total points are equal to 2+3=5).

Help Mile to calculate the number of ways he can choose a set of 6 questions.

Input

line 1: N, the number of questions in the collection
line 2: N integers P₁,P₂, P₃,...,P_N separated with one space, where P_i is the number of points the i^th question worths.

Subtasks

(8 points) 6 ≤ N ≤ 20, 1 ≤ P_i ≤ 10 000 000
(15 points) 6 ≤ N ≤ 3000, 1 ≤ P_i ≤ 10 000 000. There are exactly 3 different values in the list P₁,P₂, P₃,...,P_N.
(20 points) 6 ≤ N ≤ 3000, 1 ≤ P_i ≤ 10 000 000. Each number that is in the list P₁,P₂, P₃,...,P_N appears exactly twice.
(12 points) 6 ≤ N ≤ 150, 1 ≤ P_i ≤ 10 000 000
(15 points) 6 ≤ N ≤ 1000, 1 ≤ P_i ≤ 1 000
(10 points) 6 ≤ N ≤ 1000, 1 ≤ P_i ≤ 10 000 000
(20 points) 6 ≤ N ≤ 3 000, 1 ≤ P_i ≤ 10 000 000

Output

line 1: one integer, the number of ways professor Mile can choose the set of questions.

Constraints

Time limit: 1 second
Memory limit: 500 megabytes

Examples

input
7
2 2 4 5 3 3 5

output
1

input
7
2 2 3 3 5 5 5

output
3

input
6
5 5 5 5 5 5

output
0

Explanation for test case 1: As explained above, one set of questions professor Mile can choose is: {1,2,4,5,6,7}. In fact this is the only way he can choose a set of questions as required in the problem.

Explanation for test case 2: There are 3 possible sets of 6 questions that can be distributed to all 4 students according to the given rule. These sets are: {1,2,3,4,5,6},{1,2,3,4,5,7} and {1,2,3,4,6,7}. Hence, professor Mile has 3 ways of choosing a set of 6 questions.

Explanation for test case 3: There is no possible way he can choose a set of 6 questions.