牛牛的数字集合

题号：NC234936
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

“还有什么能比一道解不出的数学题更让人崩溃呢？” --- 某985落榜考生

牛牛有 $n$ 个数字，每个数字的范围都在 $1 \sim 10^6$ 以内。

它想请你帮它把这 $n$ 个数划分为任意 $m$ 个集合 $(1 \leq m \leq n)$ 使得：

1、每个数都在一个确定的集合中

2、每个集合中都至少有一个数

牛牛想使得最后分成的 $m$ 个集合的价值和最小，定义每个集合的价值为：集合中数的乘积的 $m$ 次方。

由于最小价值和可能十分大所以只需要告诉牛牛这个价值和模 $10^9+7$ 之后的结果就可以了。

第一行一个整数 $n$ 。

第二行 $n$ 个整数 $a_1 \sim a_n$ 。

$1 \leq n,a_i \leq 10^6$

一个整数代表价值和最小的划分方式下的价值和模 $10^9+7$ 之后的结果。

示例1

复制

2
1 2

复制

划分为一个集合：
划分为两个集合：