{"raw_statement":[{"iden":"statement","content":"Маленький Леша очень любит рисовать домики. Он готов часами рисовать домики разных форм и размеров. Как-то раз Леша попал на одну Очень Серьезную Олимпиаду. Чтобы справиться с волнением, он решил прибегнуть к любимому занятию и нарисовать много-много домиков. \n\nЛеша считает, что множество из шести отрезков образует домик, если можно выбрать три из них так, что они образуют равнобедренный треугольник, а из оставшихся трех отрезков и основания треугольника можно составить прямоугольник (смотри рисунок). \n\nУ Леши в запасе есть множество отрезков, пронумерованных от 1 до n. Лешу очень интересует, сколькими способами можно выбрать шесть отрезков из множества таким образом, чтобы из них можно было составить домик. Две шестерки отрезков считаются различными, если в одной из шестерок найдется отрезок, которого нет в другой шестерке. \n\nВ первой строке дано целое число n (6 ≤ n ≤ 105) – количество отрезков. \n\nВо второй строке даны n целых чисел ai через пробел – длины отрезков (1 ≤ ai ≤ 109).\n\nВыведите единственное число – ответ на задачу. Так как Леша еще маленький и боится больших чисел, ответ нужно вывести по модулю 109 + 9.\n\n"},{"iden":"входные данные","content":"В первой строке дано целое число n (6 ≤ n ≤ 105) – количество отрезков. Во второй строке даны n целых чисел ai через пробел – длины отрезков (1 ≤ ai ≤ 109)."},{"iden":"выходные данные","content":"Выведите единственное число – ответ на задачу. Так как Леша еще маленький и боится больших чисел, ответ нужно вывести по модулю 109 + 9."},{"iden":"примеры","content":"Входные данные61 1 1 1 1 1Выходные данные1Входные данные71 1 1 1 1 2 2Выходные данные5"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ P $ be a strictly convex polygon with $ n $ vertices, given in clockwise order by coordinates $ (x_i, y_i) \\in \\mathbb{Z}^2 $, $ i = 1, \\dots, n $, where $ 3 \\leq n \\leq 100 $.\n\n**Constraints**  \n1. $ P $ is strictly convex: all interior angles $ < \\pi $, and no three vertices are collinear.  \n2. The polygon is simple and closed.\n\n**Objective**  \nDetermine whether $ P $ can be partitioned into exactly 2017 parallelograms, each with non-zero area, such that their union is $ P $ and their interiors are pairwise disjoint.","simple_statement":"Can a strictly convex polygon with n vertices be cut into exactly 2017 parallelograms?","has_page_source":false}