Renk Kavanozu#13111

Renk Kavanozu

1,5 saniye
256 megabayt

Bohdana, soldan sağa 'den 'ye kadar numaralandırılmış tahtadan oluşan bir çiti yeniden boyuyor. numaralı tahta şu anda c_i rengine sahip. Renkler pozitif tam sayılardır ve birden fazla tahta aynı renge sahip olabilir.

Çitteki boya henüz ıslak olduğundan Bohdana çiti fırça darbeleriyle yeniden boyuyor. Bir darbede 1 \le l \le r \le n olacak şekilde iki tahta ve seçer, kuru bir fırçayla tahtasının mevcut rengini alır ve fırçayı sağa doğru tahtasına kadar çeker. Darbeden sonra l, l+1, \ldots, r tahtalarının hepsi, darbeden hemen önce tahtasının sahip olduğu rengi alır; diğer tahtalar değişmez.

Bohdana arka arkaya istediği sayıda, muhtemelen hiç, darbe yapabilir. Çitin kaç farklı boyanışını elde edebilir? İki boyanış, en az bir tahtanın renkleri farklıysa farklı sayılır. Başlangıçtaki boyanış da sayılır.

Cevap çok büyük olabileceğinden, onu moduna göre yazdırın.

Giriş

İlk satırda bir tam sayı (1 \le t \le 5000) — test durumlarının sayısı verilir.

Her test durumu iki satırdan oluşur. İlk satırda bir tam sayı (1 \le n \le 5000) — tahtaların sayısı verilir. İkinci satırda tam sayı c_1, c_2, \ldots, c_n (1 \le c_i \le 10^9) — tahtaların soldan sağa renkleri verilir.

Tüm test durumları üzerinden değerlerinin toplamı 'i aşmaz.

Çıktı

Her test durumu için bir tam sayı — Bohdana'nın elde edebileceği farklı boyanışların sayısını moduna göre yazdırın.

Örnekler

Örnek 1

Loading
Loading

Not

Birinci test durumunda çit (1, 2, 3) şeklindedir ve mümkün olan boyanış şunlardır: (1, 2, 3), (1, 1, 3), (1, 2, 2), (1, 1, 2) ve (1, 1, 1). Örneğin, (1, 1, 2) boyanışı önce (1, 2, 2) veren l = 2, r = 3 darbesi, ardından l = 1, r = 2 darbesiyle elde edilir. (1, 3, 2) boyanışı elde edilemez. Şekilde bu iki darbe gösterilmiştir: çitin üzerindeki ok fırçanın izlediği yoldur.

İkinci test durumunda mümkün olan boyanış şunlardır: (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) ve (5, 5, 5, 5). Örneğin, (5, 7, 7, 5) boyanışı önce l = 3, r = 4 darbesi, ardından l = 2, r = 3 darbesiyle elde edilir.

Üçüncü test durumunda tüm tahtalar zaten aynı renktedir ve hiçbir darbe hiçbir şeyi değiştirmez.