T-shirts#4814
At today's exercise session, LKSH students lined up in a row. Naturally, the students wear T-shirts of different colors. Boris Andriyevich, our esteemed physical education teacher, noticed that he can ask some students to sit down so that, for the students who remain standing, the sequence of T-shirt colors (from left to right) is the same as from right to left — that is, it forms a palindrome.
For example, if Masha came in a green T-shirt, Pasha in yellow, Seriyozha in red, and Vanya in green, Boris could ask Pasha to sit down, and the resulting sequence would be "green, red, green," which is a palindrome. Similarly, he could ask Seriyozha to sit down (yielding "green, yellow, green"), he could ask both Pasha and Seriyozha to sit down, or he could leave just one of the four children standing. In total, there are ways to make the sequence of colors a palindrome.
Help Boris Andriyevich determine the number of ways to ask some of the LKSH students to sit down so that the remaining sequence of colors forms a palindrome. Since this number can be very large, output it modulo 10^9.
The first line contains the integer (1 \leq N \leq 2000) — the number of LKSH students in the row. The second line contains integers, each denoting the color of a student's T-shirt, from to 10^9. Different colors are represented by different numbers, and the same colors by the same numbers.
Output a single integer — the required number of ways modulo 10^9.
Example 1