Банка фарб#13111

Банка фарб

1,5 секунди
256 мегабайтів

Богдана перефарбовує паркан з дощок, пронумерованих від до зліва направо. Зараз дошка має колір c_i. Кольори — це додатні цілі числа, і кілька дощок можуть мати однаковий колір.

Фарба на паркані ще не висохла, тому Богдана перефарбовує його мазками. За один мазок вона вибирає дві дошки і , де 1 \le l \le r \le n, набирає сухим пензлем поточний колір дошки і веде пензель праворуч аж до дошки . Після мазка всі дошки l, l+1, \ldots, r мають той колір, який мала дошка безпосередньо перед мазком, а інші дошки не змінюються.

Богдана може зробити будь-яку кількість мазків (можливо, жодного), один за одним. Скільки різних розфарбувань паркану вона може отримати? Два розфарбування різні, якщо хоча б одна дошка має в них різні кольори. Початкове розфарбування теж враховується.

Оскільки відповідь може бути дуже великою, виведіть її за модулем .

Вхідні дані

Перший рядок містить одне ціле число (1 \le t \le 5000) — кількість тестових випадків.

Кожен тестовий випадок складається з двох рядків. Перший рядок містить ціле число (1 \le n \le 5000) — кількість дощок. Другий рядок містить цілих чисел c_1, c_2, \ldots, c_n (1 \le c_i \le 10^9) — кольори дощок зліва направо.

Сума за всіма тестовими випадками не перевищує .

Вихідні дані

Для кожного тестового випадку виведіть одне ціле число — кількість різних розфарбувань, які може отримати Богдана, за модулем .

Приклади

Приклад 1

Loading
Loading

Примітка

У першому тестовому випадку паркан має вигляд (1, 2, 3), і можливі розфарбувань: (1, 2, 3), (1, 1, 3), (1, 2, 2), (1, 1, 2) і (1, 1, 1). Наприклад, (1, 1, 2) виходить мазком l = 2, r = 3, який дає (1, 2, 2), а потім мазком l = 1, r = 2. Розфарбування (1, 3, 2) отримати неможливо. На рисунку показано ці два мазки: стрілка над парканом — шлях пензля.

У другому тестовому випадку можливі розфарбувань: (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) і (5, 5, 5, 5). Наприклад, (5, 7, 7, 5) виходить мазком l = 3, r = 4, а потім мазком l = 2, r = 3.

У третьому тестовому випадку всі дошки вже мають однаковий колір, і жоден мазок нічого не змінює.