404185: GYM101445 I Домики

I. Домикиограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Маленький Леша очень любит рисовать домики. Он готов часами рисовать домики разных форм и размеров. Как-то раз Леша попал на одну Очень Серьезную Олимпиаду. Чтобы справиться с волнением, он решил прибегнуть к любимому занятию и нарисовать много-много домиков.

Леша считает, что множество из шести отрезков образует домик, если можно выбрать три из них так, что они образуют равнобедренный треугольник, а из оставшихся трех отрезков и основания треугольника можно составить прямоугольник (смотри рисунок).

У Леши в запасе есть множество отрезков, пронумерованных от 1 до n. Лешу очень интересует, сколькими способами можно выбрать шесть отрезков из множества таким образом, чтобы из них можно было составить домик. Две шестерки отрезков считаются различными, если в одной из шестерок найдется отрезок, которого нет в другой шестерке.

Входные данные

В первой строке дано целое число n (6 ≤ n ≤ 10⁵) – количество отрезков.

Во второй строке даны n целых чисел a_i через пробел – длины отрезков (1 ≤ a_i ≤ 10⁹).

Выходные данные

Выведите единственное число – ответ на задачу. Так как Леша еще маленький и боится больших чисел, ответ нужно вывести по модулю 10⁹ + 9.

ПримерыВходные данные

6
1 1 1 1 1 1

Выходные данные

1

Входные данные

7
1 1 1 1 1 2 2

Выходные данные

5