给定一个长度为 $n$ 的数组 $a_1,a_2,\dots ,a_n$，接下来进行 $n-1$ 次操作。每次选择一个下标 $x$ ，将 $a_{x}$ 和 $a_{x+1}$ 合并成 $a_{x} \times a_{x+1} \bmod 1 000 003$ ，并且你会获得 $(a_{x} - a_{x+1}) ^2$ 的分数。

所以每次操作后，数组的长度将会减 $1$，当最后只剩下一个元素时停止操作。输出最终能获得的最大分数。

输入格式

第一行一个数字 $n$。

接下来一行 $n$ 个整数 $a_1, a_2, \dots, a_n$。

输出格式

一个数，表示答案。

样例输入

3
1 2 3

样例输出

26

数据规模

所有数据保证 $1\leq n\leq 300, 1 \leq a_i \leq 10^6$。