Eveline was presented with an array a of n non-negative integers, each of which does not exceed 2022. She was interested in the question of how many different quadruples of indices exist in this array (indexes within one quadruple can coincide) such that the sum of the corresponding elements of the array is 2022. Formally, she wants to understand how many quadruples exist 1 <= i,j,k,h <= n for which ai+aj+ak+ah=2022.
February has already arrived, and Evelina still hasn't had time to calculate the answer to the question, because the array is too large. But she was able to remember it and told you about her array to get help finding the answer.
Input
The first line contains a single integer
n (1 <=
n <= 100000) - the number of array elements. The second line contains
n integers
a1,
a2,
...,
an (0 <=
ai <= 2022) - elements of Evelina's array.
Imprint
Since the answer may be too large, you need to print the remainder of the number of valid 4s divided by 1000000007 (10
9+7).
Note
In the first example, there are no fours with the sum of 2022.
In the second, quadruples (1,1,2,2), (1,2,1,2), (1,2,2,1), (2,1,1,2), (2, 1, 2, 1), (2,2,1,1).
In the third example, all 24 quadruples of pairwise distinct indices fit. For example, (1,2,3,4) or (4,1,3,2).
Examples
| # |
Input |
Output |
| 1 |
4
1 1 1 1
|
0
|
| 2 |
2
500 511
|
6
|
| 3 |
4
129 45 1000 848
|
24
|