Mountain Holidays

All submissions for this problem are available.
Some time ago, Chef discovered that more and more people have started climbing mountains every day. So he decided to build restaurant in the Ukrainian resort Bukovel (Carpathian Mountains). But there are many places to choose, so he wants to choose the best one. Let us learn how attractiveness for a location is calculated.
Next to every place, is some mountain. A Mountain is a sequence of points (0,height_{0}), (1,height_{1}), ... (n1,height_{n1}), where every two adjacent points are connected with a segment. For example, consider the mountain
(0,0), (1,2), (2,1), (3,2), (4,1), (5,3), (6,0), (7,1), (8,0) /\ /\/\/ \ / \/\
Visitors may start their climbing from some position i and finish in position j, where (i < j).They calculate the attractiveness of a mountain, as the number of different climbs that it offers. Of course, so does our Chef!
A climb from position i to position j is the sequence (i,height_{i}), ... (j,height_{j}).Two climbs, say i_{1} to j_{1} and i_{2} to j_{2}, are different if and only if
(j_{1} – i_{1} != j_{2} – i_{2}) or
height_{i1+k} – height_{i1+k1} != height_{i2+k} – height_{i2+k–1} for at least some k in the range (1, 2, ... j_{1}i_{1}).
Let us consider two climbs from the mountain we considered above
/\/ / and /\ / \ \
The first one is the climb from (0 to 3), and the second one is the climb from (4 to 6). They are different because (3  0 != 6  4). On the other hand, climbs such as (0 to 1) and (4 to 5) are the same.
Given the array, heights, find the number of different climbs that exist on the mountain which is described by the sequence of these heights. Because answer can be very large, output it modulo 1,000,000,009.
Input
First line of input contains T, the number of test cases. The first line of each test case contains N, the number of peaks. On second line of each test case, there are N numbers. The i^{th} number denotes the height of i^{th} peak.
Output
For each test case, output a single number, the number of unique climbs.
Constraints
1 ≤ T ≤ 1000
1 ≤ N ≤ 100000
Sum of N over all test cases in a file ≤ 100000
Height_{i} ≤ 1000000
Height_{i} – Height_{i1} ≤ 100 (Tourists won’t climb very steep cliffs)
Sample
Input 3 6 1 2 3 4 5 6 9 0 2 1 2 1 3 0 1 0 7 0 5 5 5 5 4 4 Output 5 31 20
Explanation
The second test case is taken from the problem statement.
Author:  witalij_hq 
Tester:  gamabunta 
Editorial  http://discuss.codechef.com/problems/MOU1H 
Tags  july13, lcp, medium, string, suffixarray, witalij_hq 
Date Added:  30032013 
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, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 