Đại Dương mới học về định nghĩa tam giác cân ở trên trường. Cậu được biết một tam giác cân là 1 tam giác mà có 2 cạnh bằng nhau.

Đại Dương cũng đã học và giải qua bài đếm bộ số tam giác (BOSOTG hay TAMHOP).

Vì vậy, Đại Dương cũng muốn ra 1 bài toán tương tự như vậy. vì lười viết đề, nên bài toán của cậu được tóm tắt như sau:

Cho \(n\) số nguyên dương. Hãy đếm số lượng bộ 3 số tam giác cân \((a_i, a_j, a_k)\) với \(i < j < k\).

Input

• Dòng đầu tiên gồm một số \(n\).
• Dòng thứ hai gồm \(n\) số nguyên dương \(a_1, a_2, a_3, \dots, a_n\) (\(a_i \leq 10^7\)).

Output

• Gồm một số duy nhất là số lượng bộ ba số tam giác cân khi chia lấy dư cho \(10^9+7\).

Example

8
5 3 2 9 5 4 9 5

22

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 300\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 10000\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \leq 10^5\).
• Subtask \(4\) (\(20\%\) số điểm): \(n \leq 10^6\).
• Subtask \(5\) (\(10\%\) số điểm): \(n \leq 10^7\).