### 问题描述

假设有一艘宇宙飞船，上面有 $n$ 个机器人，每个机器人有身上一个数字，分别为 $a_1$ 到 $a_n$ 。这些机器人的任务是在宇宙中探索行星，每次可以派出两个机器人一起探索行星，并且两个机器人的数字可以被用来计算探索的得分。具体来说，对于两个机器人，他们身上的数字分别为 $x$ 和 $y$ ，探索得分为 $\max(x^y,y^x)$ 对 $10^9+7$ 取模。一旦探索完成，可以任选一个机器人可以回到飞船上汇报信息并且它可以继续参加探索，另外一个机器人则被留在行星上驻守。当飞船上如果就剩一个机器人则探险结束，请你选择合适的安排策略使得探险结束时总探索得分最大，当然答案可能很大，请你对 $10^9+7$ 取模。

输入格式

第一行输入一个整数 $n$ ，表示机器人的数量。

第二行输入 $n$ 个整数 $a_1，a_2，...，a_n$，表示机器人身上的数字。

数据保证 $2 \leq n \leq 500$，$1 \leq a_i \leq 10^9$。

输出格式

输出一个整数表示可以得到的最大探索得分，答案对 $10^9+7$ 取模。

样例输入

4
1 2 3 4

样例输出

101

说明

样例中先派出 $3$ 号和 $4$ 号机器人去探险，可以获得探索得分 $\max(3^4,4^3)=81$，然后 $4$ 号机器人回到飞船。

接着派出 $2$ 号和 $4$ 号机器人去探险，可以获得探索得分 $\max(2^4,4^2)=16$，然后 $4$ 号机器人再次回到飞船。

接着派出 $1$ 号和 $4$ 号机器人去探险，可以获得探索得分 $\max(1^4,4^1)=4$，然后 $4$ 号机器人再次回到飞船。

飞船只剩 $4$ 号机器人，探索完毕，总得分为 $101$。