AP

0

0 votes
Problem

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

Sample Input
3
2
4
2
Sample Output
7
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

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.

Editor Image

?