Bohdana soldan sağa -dən -ə qədər nömrələnmiş taxtadan ibarət hasarı yenidən rəngləyir. Hazırda nömrəli taxtanın rəngi c_i-dir. Rənglər müsbət tam ədədlərdir və bir neçə taxta eyni rəngə malik ola bilər.
Hasardakı boya hələ yaşdır, ona görə də Bohdana onu fırça çəkmələri ilə yenidən rəngləyir. Bir çəkmədə o, 1 \le l \le r \le n şərtini ödəyən iki taxta və seçir, quru fırça ilə taxtasının cari rəngini götürür və fırçanı sağa doğru taxtasına qədər çəkir. Çəkmədən sonra bütün l, l+1, \ldots, r taxtaları çəkmədən dərhal əvvəl taxtasının malik olduğu rəngi alır, qalan taxtalar isə dəyişmir.
Bohdana ardıcıl olaraq istənilən sayda (bəlkə də heç bir) çəkmə edə bilər. O, hasarın neçə müxtəlif rənglənməsini ala bilər? Əgər heç olmasa bir taxtanın rəngi fərqlidirsə, iki rəngləmə müxtəlif sayılır. İlkin rəngləmə də nəzərə alınır.
Cavab çox böyük ola biləcəyi üçün onu moduluna görə çıxarın.
Birinci sətirdə bir tam ədəd (1 \le t \le 5000) — test hallarının sayı verilir.
Hər test halı iki sətirdən ibarətdir. Birinci sətirdə tam ədəd (1 \le n \le 5000) — taxtaların sayı verilir. İkinci sətirdə tam ədəd c_1, c_2, \ldots, c_n (1 \le c_i \le 10^9) — taxtaların soldan sağa rəngləri verilir.
Bütün test halları üzrə -lərin cəmi -i aşmır.
Hər test halı üçün bir tam ədəd — Bohdananın ala biləcəyi müxtəlif rəngləmələrin sayını moduluna görə çıxarın.
Nümunə 1
Birinci test halında hasar (1, 2, 3) şəklindədir və mümkün rəngləmə belədir: (1, 2, 3), (1, 1, 3), (1, 2, 2), (1, 1, 2) və (1, 1, 1). Məsələn, (1, 1, 2) rəngləməsi əvvəlcə (1, 2, 2) verən l = 2, r = 3 çəkməsi, sonra isə l = 1, r = 2 çəkməsi ilə alınır. (1, 3, 2) rəngləməsini almaq mümkün deyil. Şəkildə bu iki çəkmə göstərilib: hasarın üstündəki ox fırçanın yoludur.
İkinci test halında mümkün rəngləmə belədir: (5, 7, 5, 7), (5, 7, 5, 5), (5, 7, 7, 5), (5, 7, 7, 7), (5, 5, 7, 5), (5, 5, 7, 7), (5, 5, 5, 7) və (5, 5, 5, 5). Məsələn, (5, 7, 7, 5) rəngləməsi əvvəlcə l = 3, r = 4 çəkməsi, sonra isə l = 2, r = 3 çəkməsi ilə alınır.
Üçüncü test halında bütün taxtalar artıq eyni rəngdədir və heç bir çəkmə heç nəyi dəyişmir.