给定一个长度为 n 的数组 a1,a2,…,an,接下来进行 n−1 次操作。每次选择一个下标 x ,将 ax 和 ax+1 合并成 ax×ax+1mod1000003 ,并且你会获得 (ax−ax+1)2 的分数。
所以每次操作后,数组的长度将会减 1,当最后只剩下一个元素时停止操作。输出最终能获得的最大分数。
输入格式
第一行一个数字 n。
接下来一行 n 个整数 a1,a2,…,an。
输出格式
一个数,表示答案。
样例输入
3
1 2 3
样例输出
26
数据规模
所有数据保证 1≤n≤300,1≤ai≤106。