Богдана перефарбовує паркан з дощок, пронумерованих від до зліва направо. Зараз дошка має колір 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
У першому тестовому випадку паркан має вигляд (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.
У третьому тестовому випадку всі дошки вже мають однаковий колір, і жоден мазок нічого не змінює.