Maxim and Progressions

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Maxim likes arithmetic progressions and does not like sequences which are not arithmetic progressions.
Now he is interested in the question: how many subsequences of his sequence a, consisting of n elements, are not arithmetic progressions. Sequence s[1], s[2], ..., s[k] is called a subsequence of sequence a[1], a[2], ..., a[n], if there will be such increasing sequence of indices i[1], i[2], ..., i[k] (1 ≤ i[1] < i[2] < ... < i[k] ≤ n), that a[i[j]] = s[j]. In other words, sequence s can be obtained from the a by deleting some elements. Sequence s[1], s[2], ..., s[k] is called an arithmetic progression, if it can be represented as :
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains an integer n — the number of elements in the sequence. The next line of the test case contains n integer, a[1], a[2], ..., a[n] — elements of the sequence.
Output
For each test case print the remainder of the division the answer on 1000000007 (10^9 + 7). All answers print on different lines.
Constraints
1 ≤ T ≤ 10
1 ≤ n ≤ 200000
1 ≤ a[i] ≤ 100
Example
Input: 2 1 1 3 1 2 1 Output: 0 1
Author:  sereja 
Editorial  http://discuss.codechef.com/problems/MAXPR 
Tags  combinatorics, dynamicprogramming, easy, june14, sereja 
Date Added:  25052013 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions