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