Горнолыжный курорт
Совсем недавно Петя Пяточкин открыл для себя, что люди с каждым днём всё больше любят бродить в горах. И тогда он решил построить ресторан в Буковеле. Но ведь построить можно где угодно, были бы деньги. С финансами у Пети всё нормально, дело за малым - нужно только определить наилучшее место. Определим, как определяется красота места.
Вблизи каждого места имеется горный хребет. Он задаётся последовательностью точек (0, height_0), (1, height_1), ..., (n-1, height_{n-1}). Каждые две соседние точки соединены отрезком. Например, рассмотрим следующий хребет:
(0, 0) (1, 2) (2, 1) (3, 2) (4, 1) (5, 3) (6, 0) (7, 1) (8, 0)
Посетители начинают путешествие в какой-то позиции i и заканчивают в позиции j (i < j). Красота горного хребта – це количество разных возжожных путешествий. Маршрут из позиции i в позицию j – это последовательность (i, height_i), ..., (j, height_j).
Два маршрута разные, если: (j_1– i_1) ≠ (j_2– i_2) или (height_{i1+k} – height_{i1+k-1}) ≠ (height_{i2+k} – height_{i2+k–1}) хотя бы для какого-то k из интервала [1..i_1-j_1].
Рассмотрим два маршрута на хребте, изображённом выше:
и
Первый – от точки 0 до точки 3, а второй – от 4 до 6. Они разные, так как (3-0) ≠ (6-4). С другой стороны, маршруты 0..1 и 4..5 одинаковые.
Имея последовательность высот heights определите значение красоты маршрута. Ответ может быть очень большим числом, поэтому выведите его по модулю 1000000009.
Входные данные
В первой строке число Т – количество тестов (1 ≤ T ≤ 1000). В первой строке каждого теста число N – количество вершин (1 ≤ N ≤ 100000).
В следующей строке N чисел – вершины хребта (|Height_i| ≤ 10^6, |Height_i-Height_{i-1}| ≤ 100 (туристы не хотят лазить по очень крутым склонам)).
Выходные данные
Для каждого тестового случая выведите одно число – красоту горного хребта.