整数序列 $(x_1, x_2, \dots, x_n)$ 的 $boboness$ 定义为 $\prod_{i=3}^{n} w(\max\{x_{i-2}, x_{i-1}, x_i\})$。其中，$1 \le x_i \le n$，且给定了 $w(1), w(2), \dots, w(n)$ 的值。

Bobo 想知道所有满足 $1 \le x_i \le n$ 的序列的 $boboness$ 之和。由于该和可能非常大，他只需要知道结果对 $(10^9 + 7)$ 取模后的值。

输入格式

输入包含零个或多个测试用例，并以文件结束符（EOF）终止。对于每个测试用例：

第一行包含一个整数 $n$ ($3 \le n \le 2000$)。 第二行包含 $n$ 个整数 $w(1), w(2), \dots, w(n)$ ($1 \le w(i) \le 10^9$)。

保证所有测试用例的 $n$ 之和不超过 $2000$。

输出格式

对于每个测试用例，输出一个整数，表示该和对 $(10^9 + 7)$ 取模后的结果。

样例

样例输入 1

3
1 2 3
4
1 1 1 1

样例输出 1

72
256