4131：数字的人脉-2

在数字王国中有一堆 n 个数字，因为平时很无聊，所以他们会经常找朋友聊天。

但是，在王国成立之初，这些数字相互之间都不认识，因此他们需要建立人脉。

我们假设两个数字 a 和 b 相互建立人脉需要花费 F(a，b) 天，并且已知：

min(a，b) = a 和 b 中的较小值

max(a，b) = a 和 b 中的较大值

pow(a，b，c) = a 的 b 次方取余 c 的结果

F(a，b) = pow(min(a，b)，max(a，b)，1e9 + 7)

每个数字在与其它数字建立好人脉后，便成了朋友，并且朋友的朋友也是朋友。

现在请问，欲使数字王国中的 n 个数字互相之间都变成朋友，至少需要花费多少天。

第一行是一个不超过 1000 的正整数 n 表示数字王国中有多少个数字。

接下来一行 n 个不超过 10⁹ 的正整数，分别表示数字王国中的数字。

在一行中输出欲使数字王国中的 n 个数字互相之间都变成朋友，至少需要花费的天数。

4

1 2 3 4

3

TKK-ICPC Round#17