Футболки#4814
На сьогоднішньому розминковому занятті учнів ЛКШ вишикувалися в ряд. Звісно, учні носять футболки різних кольорів. Борис Андрійович, наш шановний вчитель фізкультури, помітив, що може попросити деяких учнів присісти так, що для тих, хто залишиться стояти, послідовність кольорів футболок (зліва направо) буде такою ж, як і справа наліво — тобто, вона утворює паліндром.
Наприклад, якщо Маша прийшла в зеленій футболці, Паша — у жовтій, Сергійко — у червоній, а Ваня — у зеленій, Борис може попросити Пашу присісти, і отримається послідовність "зелений, червоний, зелений", що є паліндромом. Аналогічно, він міг би попросити Сергійка присісти (тоді буде "зелений, жовтий, зелений"), або попросити присісти і Пашу, і Сергійка, або залишити стояти лише одного з чотирьох дітей. Усього існує способів зробити послідовність кольорів паліндромом.
Допоможіть Борису Андрійовичу визначити кількість способів попросити деяких учнів ЛКШ присісти так, щоб залишена послідовність кольорів утворювала паліндром. Оскільки ця кількість може бути дуже великою, виведіть її по модулю 10^9.
У першому рядку дано ціле число (1 \leq N \leq 2000) — кількість учнів ЛКШ у ряді. У другому рядку — цілих чисел, кожне з яких позначає колір футболки учня, від до 10^9. Різні кольори позначаються різними числами, а однакові — однаковими.
Виведіть одне ціле число — шукану кількість способів за модулем 10^9.
Приклад 1