На зарядку сегодня пришло \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}.