Kunal has a sequence of numbers with him. He is interested in finding out the number of subsequences of his sequence that are arithmetic progressions.
Arithmetic Progression: A sequence is an arithmetic progression if the difference between consecutive elements is constant. If the initial term of arithmetic progression is b[1] and the common difference is D then: b[n] = b[1] + (n-1)*D
Note: empty sequence or a single element sequence are arithmetic progressions.
Input
The first line of the input is an integer, the total number of elements in the sequence. Each of the next lines contains a single integer representing an element of the sequence.
Output
Let A be the number of subsequences that are arithmetic progressions. Print the value of A modulo (10^9 + 9).
Constraints
Let n be the number of elements in the input sequence. Let a[i] represent the element of the input sequence.
1<=n<=200000
1<=a[i]<=100
The different arithmetic progressions are : {}, {2}, {4}, {2}, {2, 4}, {4,2}, {2, 2}. Note that the subsequence {2} is present twice because the 2 is picked from different indices.