{"problem":{"name":"I. Домики","description":{"content":"Маленький Леша очень любит рисовать домики. Он готов часами рисовать домики разных форм и размеров. Как-то раз Леша попал на одну Очень Серьезную Олимпиаду. Чтобы справиться с волнением, он решил приб","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10144I"},"statements":[{"statement_type":"Markdown","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## Входные Данные\n\nВ первой строке дано целое число n (6 ≤ n ≤ 105) – количество отрезков. Во второй строке даны n целых чисел ai через пробел – длины отрезков (1 ≤ ai ≤ 109).\n\n## Выходные Данные\n\nВыведите единственное число – ответ на задачу. Так как Леша еще маленький и боится больших чисел, ответ нужно вывести по модулю 109 + 9.\n\n## Примеры\n\nВходные данные61 1 1 1 1 1Выходные данные1Входные данные71 1 1 1 1 2 2Выходные данные5\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10144I","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}