Dağ xizək kurortu
Petya Pyatochkin, yaxın keçmişdə insanların dağlarda dırmaşmağa olan marağının artdığını kəşf etdi. Buna görə də, Bukoveldə bir restoran tikməyə qərar verdi. Tikinti üçün yer seçimi sərbəstdir, yetər ki, maliyyə imkanları olsun. Petya'nın maliyyə vəziyyəti yaxşıdır, buna görə də yalnız ən yaxşı yeri seçmək lazımdır. Gəlin, bu yerin gözəlliyini necə müəyyən edəcəyimizi öyrənək.
Hər bir yerin yaxınlığında bir dağ silsiləsi var. Bu silsilə nöqtələrin ardıcıllığı ilə təmsil olunur: (0, height_0), (1, height_1), ..., (n-1, height_{n-1}). Hər iki qonşu nöqtə bir xətt seqmenti ilə birləşdirilir. Məsələn, aşağıdakı silsiləni nəzərdən keçirək:
(0, 0) (1, 2) (2, 1) (3, 2) (4, 1) (5, 3) (6, 0) (7, 1) (8, 0)
Ziyarətçilər müəyyən bir i mövqeyindən səyahətə başlayır və j mövqeyində bitirirlər (i < j). Dağ silsiləsinin gözəlliyi, mümkün olan fərqli səyahətlərin sayıdır. i mövqeyindən j mövqeyinə marşrut, (i, height_i), ..., (j, height_j) ardıcıllığıdır.
İki səyahət fərqlidir, əgər: (j_1– i_1) ≠ (j_2– i_2) və ya (height_{i1+k} – height_{i1+k-1}) ≠ (height_{i2+k} – height_{i2+k–1}) ən azı bir k üçün [1..i_1-j_1] intervalında.
Yuxarıdakı silsilədən iki marşrutu nəzərdən keçirək:
Birincisi 0 nöqtəsindən 3 nöqtəsinə qədərdir, ikincisi isə 4 nöqtəsindən 6 nöqtəsinə qədərdir. Onlar fərqlidirlər, çünki (3-0) ≠ (6-4). Digər tərəfdən, 0..1 və 4..5 marşrutları eynidir.
Hündürlüklərin ardıcıllığı heights verildikdə, marşrutun gözəllik dəyərini tapın. Cavab kifayət qədər böyük bir ədəd ola bilər, ona görə də onu 1000000009 modulu ilə çıxarın.
Giriş verilənləri
Birinci sətirdə T ədədi - testlərin sayı (1 ≤ T ≤ 1000). Hər bir testin birinci sətirində N ədədi - zirvələrin sayı (1 ≤ N ≤ 100000).
Növbəti sətirdə N ədəd - silsilənin zirvələri (|Height_i| ≤ 10^6, |Height_i-Height_{i-1}| ≤ 100 (turistlər çox dik yamaclarda dırmaşmaq istəmirlər)).
Çıxış verilənləri
Hər bir test halı üçün bir ədəd çıxarın - dağ silsiləsinin cazibədarlığı.