eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Горнолыжный курорт

Горнолыжный курорт

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Совсем недавно Петя Пяточкин открыл для себя, что люди с каждым днём всё больше любят бродить в горах. И тогда он решил построить ресторан в Буковеле. Но ведь построить можно где угодно, были бы деньги. С финансами у Пети всё нормально, дело за малым - нужно только определить наилучшее место. Определим, как определяется красота места.

Вблизи каждого места имеется горный хребет. Он задаётся последовательностью точек (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.

Входные данные

В первой строке число Т – количество тестов (1T1000). В первой строке каждого теста число N – количество вершин (1N100000).

В следующей строке N чисел – вершины хребта (|Height_i|10^6, |Height_i-Height_{i-1}|100 (туристы не хотят лазить по очень крутым склонам)).

Выходные данные

Для каждого тестового случая выведите одно число – красоту горного хребта.

Пример

Входные данные #1
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
Выходные данные #1
5
31
20
Автор Кожухивский Виталий
Источник Дистанционная Летняя Компьютерная Школа - лето 2013 года