На зарядку сьогодні прийшло \textbf{N} ЛКШат, вони вишикувались у ряд. Зрозуміло, діти ходять у різнокольорових футболках. Борис Андрійович, наш шановний фізрук, помітив, що можна попросити деяких дітей присісти, і тоді для дітей, які залишаться стояти, буде виконано наступне: послідовність кольорів їхніх футболок при перечисленні зліва направо буде такою ж, як і при перечисленні зправа неліво, тобто буде \textit{паліндромом}. Наприклад, якщо на зарядку прийшли Маша у зеленій футболці, Паша у жовтій, Сергій у червоній і Ваня у зеленій, то можна попросити присісти Пашу, тоді послідовність кольорів буде "зелений, червоний, зелений" як зліва направо, так і зправа наліво. Аналогічно можно попросити присісти Сергія (послідовність буде "зелений, жовтий, зелений"), Пашу і Сергія одночасно, або залишити стояти одного з чотирьох дітей. Таким чином усього є \textbf{7 }способів добитись того, щоб послідовність кольорів була паліндромом. Допоможіть Борису Андрійовичу знайти кількість способів попросити деяких ЛКШат присісти, щоб послідовність кольорів була паліндромом. Оскільки це число може бути дуже великим, виведіть його по модулю \textbf{10^9}. \InputFile Перший рядок вхідного файлу містить число \textbf{N} - кількість ЛКШат, які прийшли на зарядку (\textbf{1} ≤ \textbf{N} ≤ \textbf{2000}). Другий рядок містить \textbf{N} цілих чисел, кожне з яких задає колір футболки і змінюється у межах від \textbf{1} до \textbf{10^9}. Різні кольори задаються різними кольорами, а однакові - однаковими. \OutputFile Виведіть у вихідний файл одне число - шукану кількість способів по модулю \textbf{10^9}.