Background

In the previous problem, Xiao Y cut a lot of wooden sticks. Now she wants to put the sticks together.

Problem Description

There are $n$ wooden sticks. Choose $4$ of them, and you want to be able to form an equilateral triangle. How many such selections are there.

The answer is taken modulo $10^9+7$.

Input Format

The first line contains an integer $n$.

From the second line, there are $n$ lines. Each line contains $1$ integer. The $i$-th integer $a_i$ represents the length of the $i$-th stick.

Output Format

Output a single integer representing the answer.

4 
1
1
2
2

1

Hint

Constraints

• For $30\%$ of the testdata, it is guaranteed that $n \le 5 \times 10^3$.
• For $100\%$ of the testdata, it is guaranteed that $1 \leq n \le 10^5$, $1 \le a_i \le 5 \times 10^3$.

About the title: Due to some unforeseen circumstances, the name has been changed. We sincerely apologize.

Translated by ChatGPT 5