题目背景

题目描述

你是一位皇后。你有 $n$ 个皮蛋，每个皮蛋有一个价值 $a_i$。

两个皮蛋之间会产生一些不好的味道，第 $i$ 个皮蛋和第 $j$ 个皮蛋放在一起将会产生 $\min\{a_i^{a_j}\bmod {1000000007}，a_j^{a_i}\bmod 1000000007\}$ 的不美味度。

你要做两道菜，每道菜里都要放一些皮蛋，一个皮蛋只能且必须放在一道菜中。

一道菜的不美味度为放入这道菜里的所有皮蛋中，不美味度最大的两个皮蛋的不美味度。如果只放了一个皮蛋，则不美味度为 $0$。

两道菜的总不美味度为两道菜的不美味度中较大的那个。

你现在想让两道菜的总不美味度尽可能小。

输入格式

第一行一个整数 $n$，表示皮蛋个数。

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$，表示每个皮蛋的价值。

输出格式

一行一个整数表示答案。

样例一

input

4
1 2 1025 1024

output

1048576

explanation

把第一个皮蛋和第三个皮蛋放在第一道菜里，把第二个皮蛋和第四个皮蛋放在第二道菜里。可以证明这样得到的两道菜的总不美味度最小。

样例二

见下发文件中的 queen/ex_queen2.in 以及 queen/ex_queen2.ans。

样例三

见下发文件中的 queen/ex_queen3.in 以及 queen/ex_queen3.ans。

限制与约定

对于 $10\%$ 的数据，$n\le 10$。

对于 $40\%$ 的数据，$n\le 50$。

对于 $70\%$ 的数据，$n\le 300$。

对于 $100\%$ 的数据，$2\le n\le 2000$ ,$1 \le a_i \le 10^9$ 。