2022
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Эвелине на Новый год подарили массив $$$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$$$).

Примеры

Входные данные
4
1 1 1 1
Выходные данные
0
Входные данные
2
500 511
Выходные данные
6
Входные данные
4
129 45 1000 848
Выходные данные
24

Примечание

В первом примере не существует четверок с суммой $$$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$$$ баллов.