Гірськолижний курорт
Ще зовсім нещодавно Петя П’яточкін відкрив для себе, що люди з кожним днем все більше люблять лазити в горах. Отож він вирішив побудувати ресторан в Буковелі. Але ж побудувати можна де завгодно, лиш би були гроші. З фінансами у Петі все добре, тож потрібно лиш визначити найкраще місце. Визначимо як визначається краса місця.
Поблизу кожного місця є гірський хребет. Він задається послідовністю точок (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 (туристи не хочуть лазити по дуже крутих схилах)).
Вихідні дані
Для кожного тестового випадку виведіть одне число – привабливість гірського хребта.