Эвелине на Новый год подарили массив a из n неотрицательных целых чисел, каждое из которых не превосходит 2022. Её заинтересовал вопрос, сколько в этом массиве существует различных четверок индексов (индексы внутри одной четверки могут совпадать) таких, что сумма соответствующих элементов массива равна 2022. Формально, она хочет понять, сколько существует четверок 1 <= i,j,k,h <= n, для которых выполняется ai+aj+ak+ah=2022.
Уже наступил февраль, а Эвелина все еще не успела посчитать ответ на вопрос, потому что массив слишком большой. Но она смогла запомнить его и рассказала о своем массиве вам, чтобы получить помощь с поиском ответа.
Входные данные
В первой строке содержится одно целое число
n (1 <=
n <= 100000) - количество элементов массива. Во второй строке заданы
n целых чисел
a1,
a2,
...,
an (0 <=
ai <= 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).
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4
1 1 1 1
|
0
|
| 2 |
2
500 511
|
6
|
| 3 |
4
129 45 1000 848
|
24
|