小红的数组回文值
题号：NC277878
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

\,\,\,\,\,\,\,\,\,小红定义一个数组的回文值是：修改最少数量的元素值得该数组回文，这个次数即数组的回文值。
\,\,\,\,\,\,\,\,\,例如，\{3,2,4,3\} 的回文值是 1 ，只需要将第二个元素修改为 4 即可。
\,\,\,\,\,\,\,\,\,现在小红拿到了一个数组，她希望你求出所有子序列的回文值之和。你能帮帮她吗？

\,\,\,\,\,\,\,\,\,定义子序列为从数组中从左到右取出若干个元素（可以不取、可以全取、可以不连续）形成的数组。

输入描述:

\,\,\,\,\,\,\,\,\,第一行输入一个整数 n \left( 1\leq n \leq 2000\right) 代表数组中的元素数量。
\,\,\,\,\,\,\,\,\,第二行输入 n 个整数 a_1,a_2,\dots,a_n\left( 1\leq a_i \leq 10^9\right) 代表数组元素。

输出描述:

\,\,\,\,\,\,\,\,\,在一行上输出一个整数，代表所有子序列的回文值之和。由于答案可能很大，请将答案对 (10^9+7) 取模后输出。
示例1

输入

复制 
3
1 2 3

输出

复制 
4

说明

\,\,\,\,\,\,\,\,\,\{1,2\} 、\{1,3\} 、\{2,3\} 和 \{1,2,3\} 的回文值都是 1 。其余子序列的回文值均为 0 。
示例2

输入

复制 
4
999 999 999 999

输出

复制 
0