I

Arithmetic Subsequence

Input: Standard Input

Output: Standard Output
                                   

A sequence of numbers is said to be arithmetic if there is a constant difference between successive elements. For example {1,5,9} is an arithmetic sequence where the difference between each term is 4 and the sequence contains three elements. In this problem, given a set of numbers, you are to determine how many proper subset of this set is an arithmetic sequence. The elements in the subset must be in the same order as they occur in the superset. That is for the superset { 1,3,6},  {1,3} is a subset but not {3,1}.

 

Input

The first line of input will be a positive integer T<=100, where T denotes the number of test cases. Each case starts with a positive integer n<=250. This is followed by n non negative integers each on a new line.  The value of these integers will be less 100000001. The n integers represent the elements of the superset.

 

Output

For each case of input there will be one line of output. It will be the number of subsets which form an arithmetic sequence as described earlier. The numbers maybe very large, therefore you are to give the answer modulo 10000007. Follow sample output for exact format.

 

Sample Input                              Output for Sample Input

3

3

1

2

4

1

1

3

1

2

2

 

 

Case 1: 6

Case 2: 1

Case 3: 6

Problem setter: Shamim Hafiz, Special Thanks: Md. Arifuzzaman Arif