409685: GYM103678 H Бернард и глубокая река

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

Волга — глубокая река, причем от берега к берегу глубина может значительно меняться. Бернард сконструировал робота, который умеет выравнивать глубину участка реки. Робот выбирает два участка дна с различной глубиной $$$X$$$ и $$$Y$$$ соответственно, и получает в результате один участок глубиной $$$X \cdot Y + X + Y$$$. Процесс продолжается до тех пор, пока вся река не будет иметь одинаковую глубину. Теперь Бернард хочет узнать, какую наибольшую глубину может получить робот, выбирая участки дна каким-либо образом.

Напишите программу, которая по заданному описанию глубины участков реки определяет наибольшую возможную глубину реки, которую может получить робот. Поскольку глубина может оказаться очень большой, необходимо вывести остаток от деления результата на $$$ 10^9 + 9$$$.

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

Первая строка входных данных содержит одно целое число $$$N$$$ $$$(1 \le N \le 10^4)$$$ — количество участков дна реки.

Вторая строка входных данных содержит $$$N$$$ целых положительных чисел $$$D_i$$$ $$$(1 \le D_i \le 10^4)$$$ — глубины соответствующих участков реки.

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

В единственной строке выходных данных выведите одно целое число — значение наибольшей возможной глубины по модулю $$$10^9 + 9$$$.

Система оценки

Группа	Доп. ограничения	Баллы	Требуемые подзадачи	Тип проверки
$$$1$$$	$$$N \le 8$$$	$$$20$$$	—	Полная
$$$2$$$	$$$N, D_i \le 100$$$	$$$30$$$	—	Полная
$$$3$$$	—	$$$50$$$	$$$1,2$$$	Полная

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

3
1 2 3

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

23

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

2
100 100

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

100