Задача №114569. 2022
Эвелине на Новый год подарили массив \(a\) из \(n\) неотрицательных целых чисел, каждое из которых не превосходит \(2022\). Её заинтересовал вопрос, сколько в этом массиве существует различных четверок индексов (индексы внутри одной четверки могут совпадать) таких, что сумма соответствующих элементов массива равна 2022. Формально, она хочет понять, сколько существует четверок \( 1\leq i, j, k, h \leq n\), для которых выполняется \(a_i + a_j + a_k + a_h = 2022\).
Уже наступил февраль, а Эвелина все еще не успела посчитать ответ на вопрос, потому что массив слишком большой. Но она смогла запомнить его и рассказала о своем массиве вам, чтобы получить помощь с поиском ответа.
В первой строке содержится одно целое число \(n\) (\(1 \leq n \leq 100\,000\)) — количество элементов массива. Во второй строке заданы \(n\) целых чисел \(a_1, a_2, \ldots, a_n\) (\(0 \leq a_i \leq 2022\)) — элементы массива Эвелины.
Так как ответ может быть слишком большим, вам необходимо вывести остаток от деления количества подходящих четверок на \(1000000007\) (\(10^9 + 7\)).
В первом примере не существует четверок с суммой \(2022\).
Во втором подходят четверки \((1, 1, 2, 2)\), \((1, 2, 1, 2)\), \((1, 2, 2, 1)\), \((2, 1, 1, 2)\), (\(2, 1, 2, 1\)), \((2, 2, 1, 1)\).
В третьем примере подходят все 24 четверки попарно различных индексов. Например, \((1, 2, 3, 4)\) или \((4, 1, 3, 2)\).
В данной задаче \(50\) тестов, помимо тестов из условия, каждый из них оценивается в \(2\) балла. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования.
Решения, корректно работающие при \(1\leq n \leq 30\), наберут не менее \(10\) баллов.
Решения, корректно работающие при \(1\leq n \leq 150\), наберут не менее \(30\) баллов.
Решения, корректно работающие при \(1\leq n \leq 1500\), наберут не менее \(50\) баллов.
4 1 1 1 1
0
2 500 511
6
4 129 45 1000 848
24